oj.uz

Submission #899227

# Submission time Handle Problem Language Result Execution time Memory
899227 2024-01-05T15:55:47 Z _uros9 XOR (IZhO12_xor) C++17
0 / 100
 198 ms 129736 KB 
#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=35'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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62036 KB Output is correct
2 Correct 40 ms 61936 KB Output is correct
3 Correct 40 ms 62040 KB Output is correct
4 Correct 40 ms 62056 KB Output is correct
5 Correct 47 ms 62288 KB Output is correct
6 Correct 49 ms 62464 KB Output is correct
7 Correct 48 ms 62300 KB Output is correct
8 Correct 50 ms 62492 KB Output is correct
9 Correct 103 ms 63448 KB Output is correct
10 Correct 100 ms 63436 KB Output is correct
11 Correct 97 ms 63436 KB Output is correct
12 Correct 92 ms 63448 KB Output is correct
13 Correct 95 ms 63436 KB Output is correct
14 Correct 89 ms 63436 KB Output is correct
15 Correct 89 ms 63288 KB Output is correct
16 Correct 91 ms 63440 KB Output is correct
17 Runtime error 198 ms 129736 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -