Cod sursa(job #2230958)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 12 august 2018 15:52:05
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) std::cerr << #x << " = " << x << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("xormax.in");
ofstream g ("xormax.out");

const int MAXBIT = 21;

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

Trie *root = new Trie, *node0 = new Trie, *node1 = new Trie;
int start, stop, ans;

void update (int sum, int _pos) {
    node0 = root;
    node1 = root;
    int curr = 0;
    for (int bit = MAXBIT; bit >= 0; --bit) {
        int _son = ((sum & (1 << bit)) != 0);
        if (node0 -> son[_son] == NULL) {
            node0 -> son[_son] = new Trie;
        }
        node0 = node0 -> son[_son];
        node0 -> pos = _pos;

        if (node1 -> son[1 ^ _son] != NULL) {
            node1 = node1 -> son[1 ^ _son];
            curr += (1 << bit);
        } else {
            node1 = node1 -> son[_son];
        }
        if (bit == 0 && curr > ans) {
            ans = curr;
            stop = _pos;
            start = 1 + node1 -> pos;
        }
    }
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL_DEFINE
	freopen (".in", "r", stdin);
#endif
    int n;
	f >> n;
    ans = -1;
    update (0, -1);
    for (int i = 0, num, sum = 0; i < n; ++i) {
        f >> num;
        sum ^= num;
        update (sum, i);
    }

    g << ans << ' ' << start + 1 << ' ' << stop + 1 << '\n';

    f.close();
    g.close();
    return 0;
}