# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
418450 |
2021-06-05T11:29:39 Z |
Runtime_error_ |
XOR (IZhO12_xor) |
C++14 |
|
264 ms |
90356 KB |
#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int inf = 25e4+9,lg = 32;
ll n,k,a[inf],pre[inf];
pair<ll,ll> ans;
struct Trie{
ll cnt = 0,MinIdx = inf;
Trie *a[2] = {0};
Trie(){
cnt = 0,MinIdx = inf;
a[0] = a[1] = NULL;
}
void insert(ll bit,ll num,ll idx){
cnt++;
MinIdx = min(MinIdx,idx);
if(bit == -1)
return ;
bool CurBit = num & (1ll<<bit);
if(a[CurBit] == NULL)
a[CurBit] = new Trie();
a[CurBit]->insert(bit-1,num,idx);
}
ll query(ll bit,ll PreXor){
if(cnt == 0 || bit == -1)
return MinIdx;
bool PreBit = PreXor & (1ll<<bit);
bool KBit = k & (1ll<<bit);
if(a[0] == NULL)
a[0] = new Trie();
if(a[1] == NULL)
a[1] = new Trie();
if(KBit == 0){
if(PreBit)
return min(a[1]->query(bit-1,PreXor),a[0]->MinIdx);
else
return min(a[0]->query(bit-1,PreXor),a[1]->MinIdx);
}
else {
if(PreBit)
return a[0]->query(bit-1,PreXor);
else
return a[1]->query(bit-1,PreXor);
}
}
};
Trie *root = new Trie();
signed main(){
scanf("%lld%lld",&n,&k);
for(ll i=1;i<=n;i++){
scanf("%lld",a+i);
pre[i] = pre[i-1]^a[i];
root->insert(lg,pre[i-1],i-1);
ans = max(ans,mp(i - root->query(lg,pre[i]),-i));
}
assert(ans.first > 0 );
printf("%lld %lld\n",-ans.second-ans.first+1,ans.first);
}
Compilation message
xor.cpp: In function 'int main()':
xor.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%lld%lld",&n,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~
xor.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%lld",a+i);
| ~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
10 ms |
2636 KB |
Output is correct |
6 |
Correct |
13 ms |
3148 KB |
Output is correct |
7 |
Correct |
14 ms |
3276 KB |
Output is correct |
8 |
Correct |
22 ms |
3412 KB |
Output is correct |
9 |
Correct |
95 ms |
42256 KB |
Output is correct |
10 |
Correct |
101 ms |
42436 KB |
Output is correct |
11 |
Correct |
136 ms |
42224 KB |
Output is correct |
12 |
Correct |
97 ms |
42276 KB |
Output is correct |
13 |
Correct |
105 ms |
42440 KB |
Output is correct |
14 |
Correct |
103 ms |
42464 KB |
Output is correct |
15 |
Correct |
106 ms |
42516 KB |
Output is correct |
16 |
Correct |
100 ms |
42264 KB |
Output is correct |
17 |
Correct |
262 ms |
90272 KB |
Output is correct |
18 |
Correct |
258 ms |
90320 KB |
Output is correct |
19 |
Correct |
264 ms |
90356 KB |
Output is correct |
20 |
Correct |
262 ms |
90268 KB |
Output is correct |