| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 704202 | assem_albitar | XOR (IZhO12_xor) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define assem ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll n,k=31,x;
vector<ll> v;
ll id,mx=-1;
struct trie
{
ll mn;
trie* child[2];
trie()
{
mn=INT_MAX;
memset(child,0,sizeof child);
}
void add(int i,bitset<32> b,int id)
{
if(i==-1)
{
mn=min(mn,id);
return;
}
if(child[b[i]]==0)child[b[i]]=new trie();
child[b[i]]->add(i-1,b,id);
if(child[0]!=0)mn=min(mn,child[0]->mn);
if(child[1]!=0)mn=min(mn,child[1]->mn);
}
ll get(int i,bitset<32> b1,bitset<32> b2,ll m)
{
if(i==-1)
{
m=min(mn,m);
return m;
}
if(!b2[i])
{
if(child[!b1[i]]!=0)
{
m=min(m,child[!b1[i]]->mn);
}
if(child[b1[i]]!=0)return child[b1[i]]->get(i-1,b1,b2,m);
return m;
}
else
{
if(child[!b1[i]]!=0)
return child[!b1[i]]->get(i-1,b1,b2,m);
return m;
}
}
};
int main()
{
assem
cin>>n>>x;
trie* root=new trie();
bitset<32> b=0;root->add(k,b,0);
for(int i=0;i<n;i++)
{
ll q;
cin>>q;
v.push_back(q);
}
ll pre=0;
bitset<32> bb=x;
for(int i=0;i<n;i++)
{
pre^=v[i];
b=pre;
ll c=root->get(k,b,bb,INT_MAX);
if(i-c+1>mx)
{
mx=i-c+1;
id=c+1;
}
root->add(k,b,i+1);
}
cout<<id<<' '<<mx<<endl;
}