Hey CF Community! I have done this question ( https://codeforces.com/contest/1300/problem/C ) using prefix and suffix arrays but getting WA. As explained in the editorial firstly I calculated prefix and suffix value (~a[0])&(~a[1])... for each location. Then multiplied by a[i] for each i. But, I am getting WA. Following is my code. Please feel free to help. Thanks. ↵
↵
↵
↵
↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
#define forn(i,l,r) for(int i=l;i<r;i++)↵
#define fore(i,n) forn(i,0,n)↵
↵
int a[100001];↵
int prefix[100001],suffix[100001];↵
int main()↵
{↵
int n;↵
↵
cin>>n;↵
↵
fore(i,n)↵
cin>>a[i];↵
↵
int ipos=0;↵
↵
forn(i,0,n)↵
{↵
if(i==0)↵
prefix[0]=1073741823;↵
else prefix[i]=prefix[i-1]&(~(a[i-1]));↵
// cout<<prefix[i]<<" ";↵
}↵
// cout<<endl;↵
↵
for(int i=n-1;i>=0;i--)↵
{↵
if(i==n-1)↵
suffix[i]=1073741823;↵
else suffix[i]=(~a[i+1])&(suffix[i+1]);↵
// cout<<suffix[i]<<" ";↵
}↵
// cout<<endl;↵
int max_val=INT_MIN;↵
for(int i=0;i<=n-1;i++) ↵
{↵
// cout<<(prefix[i]&suffix[i])<<" ";↵
if(a[i]&(prefix[i]&suffix[i])>max_val)↵
{↵
max_val=a[i]&(prefix[i]&suffix[i]);↵
ipos=i;↵
}↵
}↵
// cout<<endl;↵
cout<<a[ipos];↵
↵
fore(i,n)↵
if( ipos!=i)↵
cout<<" "<<a[i];↵
↵
return 0;↵
}
↵
↵
↵
↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
#define forn(i,l,r) for(int i=l;i<r;i++)↵
#define fore(i,n) forn(i,0,n)↵
↵
int a[100001];↵
int prefix[100001],suffix[100001];↵
int main()↵
{↵
int n;↵
↵
cin>>n;↵
↵
fore(i,n)↵
cin>>a[i];↵
↵
int ipos=0;↵
↵
forn(i,0,n)↵
{↵
if(i==0)↵
prefix[0]=1073741823;↵
else prefix[i]=prefix[i-1]&(~(a[i-1]));↵
// cout<<prefix[i]<<" ";↵
}↵
// cout<<endl;↵
↵
for(int i=n-1;i>=0;i--)↵
{↵
if(i==n-1)↵
suffix[i]=1073741823;↵
else suffix[i]=(~a[i+1])&(suffix[i+1]);↵
// cout<<suffix[i]<<" ";↵
}↵
// cout<<endl;↵
int max_val=INT_MIN;↵
for(int i=0;i<=n-1;i++) ↵
{↵
// cout<<(prefix[i]&suffix[i])<<" ";↵
if(a[i]&(prefix[i]&suffix[i])>max_val)↵
{↵
max_val=a[i]&(prefix[i]&suffix[i]);↵
ipos=i;↵
}↵
}↵
// cout<<endl;↵
cout<<a[ipos];↵
↵
fore(i,n)↵
if( ipos!=i)↵
cout<<" "<<a[i];↵
↵
return 0;↵
}