Submission #899230

#	Time	Username	Problem	Language	Result	Execution time	Memory
899230		_uros9	XOR (IZhO12_xor)	C++17	100 / 100	298 ms	179612 KiB

xor

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long

using namespace std;

const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;

int N=100'000*30+9;
vector<vector<int>> trie(N,vector<int>(2,0));
int ind_c=0,rez,k=0,x;
vector<int> ind(N,100000000);
vector<int> niz(0);
void ubaci(int n,int indx){
    int node=0;
    for(int i=29; i>=0; i--){
        int c=(n&(1<<i))>0;
        if(!trie[node][c]){
            trie[node][c]=++ind_c;
            ind[ind_c]=indx;
        }
        node=trie[node][c];
    }
}
void query(int n,int&rezz){
    int node=0;
    for(int i=29; i>=0; i--){
        int c=(n&(1<<i))>0;
        if((x&(1<<i))>0){
            node=trie[node][1-c];
        }
        else{
            rezz=min(rezz,ind[trie[node][1-c]]);
            node=trie[node][c];
        }
        if(node==0) return;
    }
    rezz=min(rezz,ind[node]);
    return;
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("factory.in","r",stdin);
    //freopen("factory.out","w",stdout);


    int n;
    cin >> n >> x;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(!i){niz.push_back(a); continue;}
        niz.push_back(niz.back()^a);
    }
    if(n==1){
        cout << 1 << " " << 1;
        return 0;
    }
    ubaci(0,0);
    for(int i=0; i<n; i++){
        int rezz=100000000;
        query(niz[i],rezz);
        ubaci(niz[i],i+1);
        if(rezz>n) continue;
        if(i-rezz+1>k){
            rez=rezz;
            k=i-rezz+1;
        }
    }
    cout << rez+1 << " " << k;


    return 0;
}
/*
    abcde
    01234
    04321 --> 12340
              0   1
    011
    110
*/

• Subtask 1: 100 / 100