Suppose i have initial array is [0,0,1] and k = 3, then how we’ll process them.
At first second → [1,1,1]
At second second → [3,3,3]
At third second → [5,5,5]
So, the overall answer should be 15.
Am i correct?
Suppose i have initial array is [0,0,1] and k = 3, then how we’ll process them.
At first second → [1,1,1]
At second second → [3,3,3]
At third second → [5,5,5]
So, the overall answer should be 15.
Am i correct?
My approach in O(n) and O(n) space
#include<bits/stdc++.h>
#include <unordered_map>
#include <vector>
#define int long long
#define w(x) int x; cin>>x; while(x--)
int mod = (int)1e9+7;
#define maxv 9223372036854775807
#define minv -9223372036854775808
#define add push_back
#define MAX (int)1e7+7
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
pair<int,int>a[2*n];
int fl=0;;
for(int i=0;i<((2*n)-1);i++)
{
if(i<n)
{
cin>>a[i].first;
}
else
{
a[i].first=a[i%n].first;
}
a[i].second=i;
if(a[i].first)
{
fl=a[i].first;
}
}
if(!(fl))
{
cout<<"0\n";
return;
}
/* for(int i=0;i<(2*n)-1;i++)
{
cout<<a[i].first<<" ";
}cout<<endl;
for(int i=0;i<(2*n)-1;i++)
{
cout<<a[i].second<<" ";
}cout<<endl; */
int b[n],l=maxv;
for(int i=0;i<(2*n)-1;i++)
{
if(a[i].first==0)
{
b[i%n]=abs(l-i);
}
else
{
b[i%n]=0;
l=i;
}
}
l=maxv;
for(int i=((2*n)-2);i>=0;i--)
{
if(a[i].first==0)
{
b[i%n]=min(abs(l-i),b[i%n]);
}
else
{
b[i%n]=0;
l=i;
}
}
/* for(int i=0;i<n;i++)
{
cout<<b[i]<<" ";
}cout<<endl; */
int ans=0;
for(int i=0;i<n;i++)
{
ans+=a[i].first;
int d=max((int)0,k-b[i]);
ans+=(d*2);
}
cout<<ans<<endl;
}
/* FOR STRINGS WHOLE LINE INPUT UISNG
string s;
getline(cin,s);
*/
/* IF AMOUNT OF DATA IS UNKNOWN THEN
while(cin>>x)
{
// CODE
}
*/
/* RANGE OF INT
-2 power 31 to 2 power 31 -1
RANGE OF LONG LONG
power 63
*/
// x=(x+m)%m;
// to compare double
/* if(abs(a-b)<1e-9)
{
equal
}
*/
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
// pre();
int t;
cin >> t;
while (t--)
{
solve();
}
}