Cod sursa(job #2770669)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 22 august 2021 16:31:37
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>
#define SIGMA 2
#define NMAX 100003

using namespace std;

int val;
int s[NMAX];

struct Trie {
    int idx;
    Trie *t[SIGMA];
    Trie() {
        for(int i = 0; i < SIGMA; i++) {
            t[i] = NULL;
        }
    }
    void add(int num) {
        Trie *node = this;
        for(int i = 20; i >= 0; i--) {
            int idx = (num >> i) & 1;// 0 sau 1
            if(node->t[idx] == NULL) {
                node->t[idx] = new Trie();
            }
            node = node->t[idx];
            node->idx = val;
        }
    }
    int query(int num) {
        int ans = num;
        Trie *node = this;

        for(int i = 20; i >= 0; i--) {
            int idx = 1 ^ ((num >> i) & 1);// 0 sau 1
            if(node->t[idx] == NULL) {
                ans -= (1 ^ idx)<<i;
                node = node->t[1 ^ idx];
            }else {
                ans += idx << i;
                node = node->t[idx];
            }
        }
        val = node->idx;
        return ans;

    }
};


int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n; scanf("%d",&n);
    Trie *root = new Trie();
    root->add(0);
    for(int i = 1; i <= n; i++) {
        int x; scanf("%d",&x);
        s[i] = s[i-1] ^ x;
    }
    int sol = -1,x ,y;
    for(int i = 1; i <= n; i++) {
        int nr = root->query(s[i]);
        if(sol < nr) {
            sol = nr;
            y = i;
            x = val;
        }
        val = i;
        root->add(s[i]);
    }
    printf("%d %d %d\n",sol, x+1, y);

}