oj.uz

Submission #899230

# Submission time Handle Problem Language Result Execution time Memory
899230 2024-01-05T15:56:24 Z _uros9 XOR (IZhO12_xor) C++17
100 / 100
 298 ms 179612 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=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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 176344 KB Output is correct
2 Correct 129 ms 176516 KB Output is correct
3 Correct 112 ms 176336 KB Output is correct
4 Correct 114 ms 176440 KB Output is correct
5 Correct 122 ms 176744 KB Output is correct
6 Correct 121 ms 176596 KB Output is correct
7 Correct 124 ms 176824 KB Output is correct
8 Correct 131 ms 176876 KB Output is correct
9 Correct 168 ms 177112 KB Output is correct
10 Correct 166 ms 177068 KB Output is correct
11 Correct 169 ms 177040 KB Output is correct
12 Correct 159 ms 176984 KB Output is correct
13 Correct 168 ms 177152 KB Output is correct
14 Correct 173 ms 177036 KB Output is correct
15 Correct 169 ms 177152 KB Output is correct
16 Correct 169 ms 177088 KB Output is correct
17 Correct 292 ms 177596 KB Output is correct
18 Correct 298 ms 179412 KB Output is correct
19 Correct 287 ms 179612 KB Output is correct
20 Correct 281 ms 179584 KB Output is correct