# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
537972 | GioChkhaidze | XOR (IZhO12_xor) | C++14 | 1 ms | 340 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 250005;
int n, x, vl, ind, len = -1, indx, sz = 1;
int s[N], D[60 * N], T[60 * N][3];
inline void rec(int id) {
if (len < ind - id || (len == ind - id && id + 1 < indx)) {
len = ind - id, indx = id + 1;
}
}
inline void get(int idx, int id, int sum) {
if (id == -1) { assert(sum != vl); rec(D[idx]); return ; }
bool t0 = ((vl >> id) & 1), t1 = (t0 ^ 1);
if (T[idx][t1] && sum + (1 << id) > x) rec(D[T[idx][t1]]);
if (T[idx][t1] && sum + (1 << id) <= x) {
get(T[idx][t1], id - 1, sum + (1 << id));
}
else
if (T[idx][t0]) {
get(T[idx][t0], id - 1, sum);
}
}
inline void upd(int idx, int id) {
D[idx] = min(D[idx], ind);
if (id == -1) return ;
bool t = ((vl >> id) & 1);
if (!T[idx][t]) {
T[idx][t] = ++sz;
D[sz] = 1e9;
}
upd(T[idx][t], id - 1);
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
D[1] = 1e9;
cin >> n >> x;
for (int i = 1; i <= n; ++i) {
int y;
cin >> y;
s[i] = (s[i - 1] ^ y);
ind = i, vl = s[i];
if (s[i] >= x) rec(0);
upd(1, 30), get(1, 30, 0);
}
cout << indx << " " << len << "\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |