Cod sursa(job #2400683)

Utilizator osiaccrCristian Osiac osiaccr Data 8 aprilie 2019 23:56:50
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define MAX_BIT 22

using namespace std;

struct trie {

    trie * t[2];

    int index;

    trie () {
        t[0] = t[1] = NULL;
    }

} * root;

ifstream fin ("xormax.in");
ofstream fout ("xormax.out");

int n, currXor, maxim = -1, st, dr;

void adauga (int x, int index) {

    trie * currNod = root;

    for (int i = MAX_BIT; i >= 0; -- i) {

        int currBit = bool(x & (1 << i));

        if (currNod -> t[currBit] == NULL) {
            currNod -> t[currBit] = new trie ();
        }


        currNod = currNod -> t[currBit];

    }

    currNod -> index = index;

}

void verif (int x, int finish) {

    trie * currNod = root;

    int rez = 0;

    for (int i = MAX_BIT; i >= 0; -- i) {

        int currBit = bool(x & (1 << i));

        if (currNod -> t[!currBit] != NULL) {
            rez += (1 << i);
            currNod = currNod -> t[!currBit];
        }
        else {
            currNod = currNod -> t[currBit];
        }

    }

    if (maxim < rez) {
        maxim = rez;
        st = currNod -> index + 1;
        dr = finish;
    }

}

int main () {

    fin >> n;

    root = new trie ();

    for (int i = 1; i <= n; ++ i) {
        int x;
        fin >> x;

        currXor ^= x;

        if (i != 1) {
            verif (currXor, i);
        }

        adauga (currXor, i);
    }

    fout << maxim << " " << st << " " << dr;

    return 0;
}