Submission #16864

#	Time	Username	Problem	Language	Result	Execution time	Memory
16864		murat	XOR (IZhO12_xor)	C++98	100 / 100	157 ms	81800 KiB

xor

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 250001;

int F[N << 4], S = 1, mx[N << 4], mn[N << 4], t, n, m, x, y, z, a[N], b[N], way[N << 4][2];

void insert(int x, int index) {
    int node = 1;
    ROF(i, 29, 0) {
        int t = (1 << i) & x;
        t = t != 0;
        if(!way[node][t]) way[node][t] = ++S;
        node = way[node][t];
    } F[node] = max(F[node], index);
}

pii dfs(int node) {
    if(way[node][0]) {
        pii temp = dfs(way[node][0]);
        mx[node] = max(mx[node], temp.st);
    }
    if(way[node][1]) {
        pii temp = dfs(way[node][1]);
        mx[node] = max(mx[node], temp.st);
    }
    if(mx[node] == 0)
        mx[node] = mn[node] = F[node];
    return mp(mx[node], mn[node]);
}

int solve(int node, int d, int y) {
    if(d == 0) return mx[node];
    if((x & (1 << d)) && (y & (1 << d))) {
        if(way[node][0]) return solve(way[node][0], d-1, y);
        else return 0;
    }

    if(y & (1 << d)) {
        if(way[node][1]) return max(solve(way[node][1], d-1, y), mx[way[node][0]]);
        else return mx[way[node][0]];
    }
    if(x & (1 << d)) {
        if(way[node][1]) return solve(way[node][1], d-1, y);
        else return 0;
    }
    if(way[node][0])
        return max(way[node][1], solve(way[node][0], d-1, y));
    else return mx[way[node][1]];
}

int main() {
    scanf("%d %d",&n, &x);
    FOR(i, 1, n) {
        scanf("%d", &a[i]);
        b[i] = a[i] ^ b[i-1];
        insert(b[i], i);
    }
    dfs(1);
    FOR(i, 1, n) {
        t = max(t, solve(1, 29, b[i]) - i);
    }
    FOR(i, 0, n-t)
        if((b[i+t] ^ b[i]) >= x) {
            cout << i + 1 << ' ' << t << endl;
            return 0;
        }
    return 0;
}

• Subtask 1: 100 / 100