제출 #482809

#제출 시각아이디문제언어결과실행 시간메모리
482809FatihSolakXOR (IZhO12_xor)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> #define N 250005 #define K 29 using namespace std; struct node{ int val=0,l=0,r=0; }; node trie[N * K]; int arr[N]; int cnt = 1; void add(int x,int pos){ int now = 1; for(int i=0;i<=K;i++){ if((1<<(K-i)) & x){ if(trie[now].r == 0)trie[now].r = ++cnt; now = trie[now].r; } else{ if(trie[now].l == 0)trie[now].l = ++cnt; now = trie[now].l; } trie[now].val = max(trie[now].val,pos); } } void solve(){ int n,x; cin >> n >> x; for(int i=1;i<=n;i++)cin >> arr[i]; int xr = 0; int ans = 0; int pos = 0; for(int i=n;i>=1;i--){ xr ^= arr[i]; int maxi = 0; if(xr >= x)maxi = n+1; add(arr[i],i); int now = 1; int mask = 0; for(int j=0;j<=K;j++){ if( ( 1<<(K-j)) & arr[i] ){ if((mask ^ ((1<<(K - j)) - 1)) < x){ now = trie[now].l; } else{ maxi = max(maxi, trie[trie[now].l].val); mask ^= (1<<(K-j)); now = trie[now].r; } } else{ if( (mask ^ (1<<(K-j)) ^ arr[i]) >= x){ maxi = max(maxi, trie[trie[now].r].val); now = trie[now].l; } else{ maxi = max(maxi, trie[trie[now].l].val); mask ^= (1<<(K-j)); now = trie[now].r; } } //cout << i << " " << mask << endl; if(now == 0)break; } //cout << i << " " << maxi << endl; if(ans <= maxi - i){ ans = maxi - i; pos = i; } } cout << pos << " " << ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef Local freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t=1; //cin>>t; while(t--){ solve(); } #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...