Submission #90383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90383	2018-12-21T12:42:01 Z	popovicirobert	XOR (IZhO12_xor)	C++14	100 / 100	330 ms	69920 KB

xor

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int INF = 1e9;

struct Trie {
    Trie *son[2];
    int pos;
    Trie() {
        son[0] = son[1] = NULL;
        pos = INF;
    }
};

Trie *root = new Trie;

void ins(Trie *nod, int bit, int val, int pos) {
    if(bit == -1) {
        nod -> pos = min(nod -> pos, pos);
    }
    else {
        int b = ((val & (1 << bit)) > 0);
        if(nod -> son[b] == NULL) {
            nod -> son[b] = new Trie;
        }
        ins(nod -> son[b], bit - 1, val, pos);
        nod -> pos = min(nod -> pos, pos);
    }
}

int query(Trie *nod, int bit, int val, int x) {
    if(nod == NULL) {
        return INF;
    }
    if(bit == -1) {
        return nod -> pos;
    }
    else {
        if(x & (1 << bit)) {
            if(val & (1 << bit)) {
                return query(nod -> son[0], bit - 1, val, x);
            }
            else {
                return query(nod -> son[1], bit - 1, val, x);
            }
        }
        else {
            int ans = INF;
            if((val & (1 << bit)) == 0) {
                if(nod -> son[1] != NULL) {
                    ans = nod -> son[1] -> pos;
                }
                ans = min(ans, query(nod -> son[0], bit - 1, val, x));
            }
            else {
                if(nod -> son[0] != NULL) {
                    ans = nod -> son[0] -> pos;
                }
                ans = min(ans, query(nod -> son[1], bit - 1, val, x));
            }
            return ans;
        }
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, x;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> x;
    ins(root, 30, 0, 0);
    pair <int, int> ans = {0, 0};
    int sum = 0;
    for(i = 1; i <= n; i++) {
        int val;
        cin >> val;
        sum ^= val;
        int cur = query(root, 30, sum, x);
        if(i - cur > ans.second) {
            ans = {cur + 1, i - cur};
        }
        ins(root, 30, sum, i);
    }
    cout << ans.first << " " << ans.second;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	3 ms	756 KB	Output is correct
5	Correct	11 ms	1924 KB	Output is correct
6	Correct	13 ms	2068 KB	Output is correct
7	Correct	13 ms	2068 KB	Output is correct
8	Correct	15 ms	2068 KB	Output is correct
9	Correct	114 ms	26952 KB	Output is correct
10	Correct	113 ms	27924 KB	Output is correct
11	Correct	111 ms	28608 KB	Output is correct
12	Correct	111 ms	29268 KB	Output is correct
13	Correct	112 ms	30164 KB	Output is correct
14	Correct	115 ms	31036 KB	Output is correct
15	Correct	111 ms	31708 KB	Output is correct
16	Correct	107 ms	32480 KB	Output is correct
17	Correct	314 ms	64084 KB	Output is correct
18	Correct	323 ms	66028 KB	Output is correct
19	Correct	330 ms	67988 KB	Output is correct
20	Correct	321 ms	69920 KB	Output is correct