# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
319646 |
2020-11-06T00:48:22 Z |
jovan_b |
XOR (IZhO12_xor) |
C++17 |
|
172 ms |
35972 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int trie[5000005];
int sled[5000005][2];
int mn[5000005];
int cnt;
int x;
void trieadd(int v, int ind){
int node = 0;
mn[node] = min(mn[node], ind);
for(int i=29; i>=0; i--){
if(v&(1<<i)){
if(!sled[node][1]) sled[node][1] = ++cnt;
node = sled[node][1];
}
else{
if(!sled[node][0]) sled[node][0] = ++cnt;
node = sled[node][0];
}
mn[node] = min(mn[node], ind);
}
}
int query(int v){
int node = 0;
int res = 1000000;
for(int i=29; i>=0; i--){
if(x&(1<<i)){
int t = 1;
if(v&(1<<i)) t = 0;
if(!sled[node][t]) break;
node = sled[node][t];
}
else{
int t = 1;
if(v&(1<<i)) t = 0;
if(sled[node][t]){
//cout << v << " " << i << " " << t << " " << mn[sled[node][t]] << endl;
res = min(res, mn[sled[node][t]]);
}
if(!sled[node][1^t]) break;
node = sled[node][1^t];
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n;
cin >> n >> x;
if(x == 0){
cout << 1 << " " << n << "\n";
return 0;
}
for(int i=0; i<=5000000; i++) mn[i] = 5000000;
x--;
int xx = 0;
trieadd(0, 0);
int resi = 0, res = 0;
for(int i=1; i<=n; i++){
int a;
cin >> a;
xx ^= a;
int g = query(xx);
if(i-g > res){
resi = g+1;
res = i-g;
}
trieadd(xx, i);
}
cout << resi << " " << res << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19948 KB |
Output is correct |
2 |
Correct |
12 ms |
20076 KB |
Output is correct |
3 |
Correct |
12 ms |
19948 KB |
Output is correct |
4 |
Correct |
12 ms |
20076 KB |
Output is correct |
5 |
Correct |
18 ms |
20204 KB |
Output is correct |
6 |
Correct |
24 ms |
20332 KB |
Output is correct |
7 |
Correct |
20 ms |
20332 KB |
Output is correct |
8 |
Correct |
24 ms |
20332 KB |
Output is correct |
9 |
Correct |
60 ms |
26476 KB |
Output is correct |
10 |
Correct |
61 ms |
26724 KB |
Output is correct |
11 |
Correct |
63 ms |
26628 KB |
Output is correct |
12 |
Correct |
69 ms |
26468 KB |
Output is correct |
13 |
Correct |
60 ms |
26596 KB |
Output is correct |
14 |
Correct |
56 ms |
26612 KB |
Output is correct |
15 |
Correct |
59 ms |
26596 KB |
Output is correct |
16 |
Correct |
55 ms |
26592 KB |
Output is correct |
17 |
Correct |
152 ms |
34148 KB |
Output is correct |
18 |
Correct |
172 ms |
35972 KB |
Output is correct |
19 |
Correct |
146 ms |
35924 KB |
Output is correct |
20 |
Correct |
146 ms |
35940 KB |
Output is correct |