| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 704202 | assem_albitar | XOR (IZhO12_xor) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}