Submission #319646

#	Time	Username	Problem	Language	Result	Execution time	Memory
319646		jovan_b	XOR (IZhO12_xor)	C++17	100 / 100	172 ms	35972 KiB

xor

#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;
}

• Subtask 1: 100 / 100