Submission #891738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891738	2023-12-23T20:21:50 Z	Andrey	XOR (IZhO12_xor)	C++14	100 / 100	95 ms	34348 KB

xor

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

vector<pair<int,int>> trie(1,{-1,-1});
vector<int> sm(1);
int x,ans = INT_MAX;

void ins(int p, int a, int d, int yo) {
    if(d == -1) {
        return;
    }
    if(a&(1 << d)) {
        if(trie[p].second == -1) {
            trie.push_back({-1,-1});
            sm.push_back(yo);
            trie[p] = {trie[p].first,trie.size()-1};
            ins(trie.size()-1,a,d-1,yo);
        }
        else {
            ins(trie[p].second,a,d-1,yo);
        }
    }
    else {
        if(trie[p].first == -1) {
            trie.push_back({-1,-1});
            sm.push_back(yo);
            trie[p] = {trie.size()-1,trie[p].second};
            ins(trie.size()-1,a,d-1,yo);
        }
        else {
            ins(trie[p].first,a,d-1,yo);
        }
    }
}

void calc(int p, int a, int d) {
    //cout << p << " " << d << " " << ans << endl;
    if(d == -1) {
        ans = min(ans,sm[p]);
        return;
    }
    if(x&(1 << d)) {
        if(a&(1 << d)) {
            if(trie[p].first == -1) {
                return;
            }
            calc(trie[p].first,a,d-1);
        }
        else {
            if(trie[p].second == -1) {
                return;
            }
            calc(trie[p].second,a,d-1);
        }
    }
    else {
        if(a&(1 << d)) {
            if(trie[p].first != -1) {
                ans = min(ans,sm[trie[p].first]);
            }
            if(trie[p].second != -1) {
                calc(trie[p].second,a,d-1);
            }
        }
        else {
            if(trie[p].second != -1) {
                ans = min(ans,sm[trie[p].second]);
            }
            if(trie[p].first != -1) {
                calc(trie[p].first,a,d-1);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,l = -1,big = 0;
    cin >> n >> x;
    vector<int> haha(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
        haha[i]^=haha[i-1];
    }
    ins(0,0,30,0);
    for(int i = 1; i <= n; i++) {
        ans = INT_MAX;
        calc(0,haha[i],30);
        if(i-ans > big) {
            big = i-ans;
            l = ans+1;
        }
        ins(0,haha[i],30,i);
    }
    cout << l << " " << big;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	6 ms	1240 KB	Output is correct
6	Correct	7 ms	1496 KB	Output is correct
7	Correct	8 ms	1496 KB	Output is correct
8	Correct	9 ms	1620 KB	Output is correct
9	Correct	36 ms	16712 KB	Output is correct
10	Correct	37 ms	16496 KB	Output is correct
11	Correct	35 ms	15680 KB	Output is correct
12	Correct	37 ms	17272 KB	Output is correct
13	Correct	35 ms	16188 KB	Output is correct
14	Correct	37 ms	16528 KB	Output is correct
15	Correct	36 ms	16704 KB	Output is correct
16	Correct	37 ms	16704 KB	Output is correct
17	Correct	95 ms	34348 KB	Output is correct
18	Correct	93 ms	33120 KB	Output is correct
19	Correct	92 ms	33604 KB	Output is correct
20	Correct	91 ms	34264 KB	Output is correct