Submission #90383

#	Time	Username	Problem	Language	Result	Execution time	Memory
90383		popovicirobert	XOR (IZhO12_xor)	C++14	100 / 100	330 ms	69920 KiB

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 / 100