Submission #1276373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276373		papaulo	XOR (IZhO12_xor)	C++20	100 / 100	100 ms	87428 KiB

xor

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

using ll = long long;

#define MAXI 10100100
#define MAXN 300300
int trie[MAXI][2];
int idx[MAXI];
int a[MAXN];
int n, k;
int id=0;
ll ans=0;

void insert(int v, int idd) {
    int n=0;
    for(int i=31;i>=0;i--) {
        int c=(v>>i)&1;
        int &t=trie[n][c];
        if(!t) {
            t=++id;
            idx[t]=idd;
        }
        n=t;
    }
}

int search(int v) {
    int n=0;
    int ans=0;
    for(int i=31;i>=0;i--) {
        int cv=(v>>i)&1;
        int ck=(k>>i)&1;
        int t=trie[n][cv^ck];
        if(!ck) ans=max(ans, idx[trie[n][1^cv]]);
        if(!t) {
            return ans;
        }
        n=t;
    }
    ans=max(ans, idx[n]);
    return ans;
}

int main() {
    memset(trie, 0, sizeof(trie));
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    int v=0;
    int bstK=0, bstI=0;
    for(int i=n;i>=1;i--) {
        insert(v, i+1);
        v^=a[i];
        int k=search(v)-i;
        if(k>=bstK) {
            bstK=k;
            bstI=i;
        }
    }
    cout << bstI << " " << bstK << endl;
}

• Subtask 1: 100 / 100