# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
716552 |
2023-03-30T09:57:41 Z |
vjudge1 |
XOR (IZhO12_xor) |
C++17 |
|
106 ms |
24404 KB |
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
struct segment{int l, r, id;
int size(){return r-l+1;}};
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 25e4 + 1;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;
int n, x, sz;
int nxt[maxn * 30][2];
int a[maxn], mn[maxn * 30];
void add(int x, int num){
int v = 0;
for(int i = 29; i >= 0; i--){
int c = (x >> i) & 1;
if(!nxt[v][c]) nxt[v][c] = ++sz, mn[sz] = inf;
v = nxt[v][c];
mn[v] = min(mn[v], num);
}
}
void test(){
cin >> n >> x;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] ^= a[i-1];
}
add(0, 0);
int ansi = -1, ansk = 0;
for(int i = 1; i <= n; i++){
int v = 0; int l = inf;
for(int k = 29; k >= 0; k--){
int c = (a[i] >> k) & 1;
int e = (x >> k) & 1;
if(e == 0 && nxt[v][c ^ 1]) l = min(l, mn[nxt[v][c ^ 1]]);
if(!nxt[v][c ^ e]) break;
v = nxt[v][c ^ e];
if(k == 0) l = min(l, mn[v]);
}
if(ansk < i - l){
ansi = l + 1;
ansk = i - l;
}
add(a[i], i);
}
cout << ansi << ' ' << ansk;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; t = 1;
while(t--) test();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
7 ms |
1076 KB |
Output is correct |
6 |
Correct |
7 ms |
1112 KB |
Output is correct |
7 |
Correct |
6 ms |
1108 KB |
Output is correct |
8 |
Correct |
8 ms |
1236 KB |
Output is correct |
9 |
Correct |
34 ms |
11376 KB |
Output is correct |
10 |
Correct |
30 ms |
11340 KB |
Output is correct |
11 |
Correct |
33 ms |
11312 KB |
Output is correct |
12 |
Correct |
43 ms |
11312 KB |
Output is correct |
13 |
Correct |
36 ms |
11396 KB |
Output is correct |
14 |
Correct |
31 ms |
11408 KB |
Output is correct |
15 |
Correct |
36 ms |
11428 KB |
Output is correct |
16 |
Correct |
31 ms |
11344 KB |
Output is correct |
17 |
Correct |
98 ms |
24168 KB |
Output is correct |
18 |
Correct |
106 ms |
24404 KB |
Output is correct |
19 |
Correct |
102 ms |
24316 KB |
Output is correct |
20 |
Correct |
105 ms |
24220 KB |
Output is correct |