Cod sursa(job #1509329)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 23 octombrie 2015 18:58:14
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#define MAXN 100000
#define B 21
using namespace std;

struct Trie {
    int nr;
    Trie *son[2];

    Trie() {
        nr = -1;
        son[0] = son[1] = 0;
    }
};
Trie *T = new Trie;

int pos;

void add(int x, Trie *node, int b, int ind) {
    if (b < 0) {
        node -> nr = ind;
    }

    else {
        int p = ((x >> b) & 1);

        if (node -> son[p] == 0)
            node -> son[p] = new Trie;

        add(x, node -> son[p], b - 1, ind);
    }
}

int query(int x, Trie *node, int b) {
    if (b == -1) {
        pos = node -> nr;
        return 0;
    }

    int p = ((x >> b) & 1);
    p = 1 - p;

    if (node -> son[p])
        return (p * (1 << b)) + query(x, node -> son[p], b - 1);
    else
        return ((1 - p) * (1 << b)) + query(x, node -> son[1 - p], b - 1);
}

int main () {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");

    int n;
    cin >> n;

    int x;
    cin >> x;
    add(x, T, B, 0);

    int sumx = x;
    int sol = x, l = 0, r = 0;
    for (int i = 1 ; i < n ; ++i) {
        cin >> x;
        sumx ^= x;

        if (sumx > sol) {
            sol = sumx;
            l = 0;
            r = i;
        }

        int k = query(sumx, T, B);
        if ((k ^ sumx) > sol) {
            sol = (k ^ sumx);
            l = pos + 1;
            r = i;
        }

        add(sumx, T, B, i);

    }

    cout << sol << " " << l + 1 << " " << r + 1 << "\n";
    return 0;
}