Submission #1045118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045118		Hamed_Ghaffari	XOR (IZhO12_xor)	C++17	100 / 100	95 ms	27024 KiB

xor

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back
#define SZ(x) int(x.size())
#define mins(a, b) (a = min(a, b))
#define maxs(a, b) (a = max(a, b))

const int MXN = 25e4+5;
const int INF = 1e9+7;
const int LOG = 30;

int n, x, a[MXN];
vector<int> ch[2], mn;

int new_node() {
    ch[0].pb(0), ch[1].pb(0); mn.pb(INF);
    return SZ(mn)-1;
}

void insert(int i) {
    int v = 0;
    mins(mn[v], i);
    for(int j=LOG; j>=0; j--) {
        int b = a[i]>>j & 1;
        if(!ch[b][v]) ch[b][v] = new_node();
        v = ch[b][v];
        mins(mn[v], i);
    }
}

int get(int i) {
    int v=0;
    int res=INF;
    for(int j=LOG; j>=0; j--)
        if(x>>j & 1) {
            if(!ch[(a[i]>>j&1)^1][v]) break;
            v = ch[(a[i]>>j&1)^1][v];
        }
        else {
            if(ch[(a[i]>>j&1)^1][v]) mins(res, mn[ch[(a[i]>>j&1)^1][v]]);
            if(!ch[a[i]>>j&1][v]) break;
            v = ch[a[i]>>j&1][v];
        }
    return res;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> x;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        a[i]^=a[i-1];
    }
    if(x == 0) {
        cout << "1 " << n << '\n';
        return 0;
    }
    x--;
    new_node();
    int id=-1, k=0;
    for(int i=1; i<=n; i++) {
        int j = get(i);
        if(i-j>k) id=j+1, k = i-j;
        insert(i);
    }
    cout << id << ' ' << k << '\n';
    return 0;
}

• Subtask 1: 100 / 100