# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
447573 | asbsfds | XOR (IZhO12_xor) | C++14 | 1 ms | 332 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>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;
struct node {
node *l, *r;
int mini;
node() {
mini = inf;
l = r = nullptr;
}
};
int n, x;
int niz[maxn];
node* root;
int get_value(node *tren) {
if (tren == nullptr) return inf;
return tren->mini;
}
void insert(int x, int val, int iter = 31, node* tren = root) {
if (iter < 0) {
tren->mini = val;
return;
}
node* nex;
if (x & (1 << iter)) {
if (tren->r == nullptr) tren->r = new node;
nex = tren->r;
} else {
if (tren->l == nullptr) tren->l = new node;
nex = tren->l;
}
insert(x, val, iter - 1, nex);
tren->mini = min(get_value(tren->l), get_value(tren->r));
}
int query(int x, int iter = 31, node* tren = root) {
if (tren == nullptr) return inf;
if (iter < 0) return tren->mini;
int out = inf;
if ((::x & (1 << iter)) == 0) {
if (x & (1 << iter)) out = min(query(x, iter - 1, tren->r), get_value(tren->l));
else out = min(query(x, iter - 1, tren->l), get_value(tren->r));
} else {
if (x & (1 << iter)) out = query(x, iter - 1, tren->l);
else out = query(x, iter - 1, tren->r);
}
return out;
}
int main() {
scanf("%d%d", &n, &x);
for (int i = 1; i <= n; i++)
scanf("%d", niz+i);
root = new node;
insert(0, 0);
for (int i = 1; i <= n; i++) {
niz[i] ^= niz[i - 1];
insert(niz[i], i);
}
int a = -1, k = -1;
for (int i = 1; i <= n; i++) {
int x = query(niz[i]);
//printf("debug: %d %d\n", x + 1, i);
if (k < i - x) {
a = x + 1;
k = i - x;
}
}
printf("%d %d\n", a, k);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |