Submission #319646

# Submission time Handle Problem Language Result Execution time Memory
319646 2020-11-06T00:48:22 Z jovan_b XOR (IZhO12_xor) C++17
100 / 100
172 ms 35972 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int trie[5000005];
int sled[5000005][2];
int mn[5000005];

int cnt;

int x;

void trieadd(int v, int ind){
    int node = 0;
    mn[node] = min(mn[node], ind);
    for(int i=29; i>=0; i--){
        if(v&(1<<i)){
            if(!sled[node][1]) sled[node][1] = ++cnt;
            node = sled[node][1];
        }
        else{
            if(!sled[node][0]) sled[node][0] = ++cnt;
            node = sled[node][0];
        }
        mn[node] = min(mn[node], ind);
    }
}

int query(int v){
    int node = 0;
    int res = 1000000;
    for(int i=29; i>=0; i--){
        if(x&(1<<i)){
            int t = 1;
            if(v&(1<<i)) t = 0;
            if(!sled[node][t]) break;
            node = sled[node][t];
        }
        else{
            int t = 1;
            if(v&(1<<i)) t = 0;
            if(sled[node][t]){
                //cout << v << " " << i << " " << t << " " << mn[sled[node][t]] << endl;
                res = min(res, mn[sled[node][t]]);
            }
            if(!sled[node][1^t]) break;
            node = sled[node][1^t];
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n >> x;
    if(x == 0){
        cout << 1 << " " << n << "\n";
        return 0;
    }
    for(int i=0; i<=5000000; i++) mn[i] = 5000000;
    x--;
    int xx = 0;
    trieadd(0, 0);
    int resi = 0, res = 0;
    for(int i=1; i<=n; i++){
        int a;
        cin >> a;
        xx ^= a;
        int g = query(xx);
        if(i-g > res){
            resi = g+1;
            res = i-g;
        }
        trieadd(xx, i);
    }
    cout << resi << " " << res << "\n";
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 12 ms 19948 KB Output is correct
2 Correct 12 ms 20076 KB Output is correct
3 Correct 12 ms 19948 KB Output is correct
4 Correct 12 ms 20076 KB Output is correct
5 Correct 18 ms 20204 KB Output is correct
6 Correct 24 ms 20332 KB Output is correct
7 Correct 20 ms 20332 KB Output is correct
8 Correct 24 ms 20332 KB Output is correct
9 Correct 60 ms 26476 KB Output is correct
10 Correct 61 ms 26724 KB Output is correct
11 Correct 63 ms 26628 KB Output is correct
12 Correct 69 ms 26468 KB Output is correct
13 Correct 60 ms 26596 KB Output is correct
14 Correct 56 ms 26612 KB Output is correct
15 Correct 59 ms 26596 KB Output is correct
16 Correct 55 ms 26592 KB Output is correct
17 Correct 152 ms 34148 KB Output is correct
18 Correct 172 ms 35972 KB Output is correct
19 Correct 146 ms 35924 KB Output is correct
20 Correct 146 ms 35940 KB Output is correct