Cod sursa(job #2533824)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 29 ianuarie 2020 19:12:51
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

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

struct trie{
    trie *f[2];
    int poz;
    trie(){
        f[0] = f[1] = 0;
        poz = 0;
    }
};

int st, dr, sol, n, maxim, x, nr, pozs;
int s[100005];

trie *rad;

void insereaza (trie *rad, int bit, int val, int poz) {
    if (bit == -1) {
        rad->poz = poz;
        return;
    }
    if ( ( (val >> bit) & 1 ) == 0) {
        if (rad->f[0] == NULL)
            rad->f[0] = new trie();
        insereaza (rad->f[0], bit-1, val, poz);
    }
    else {
        if (rad->f[1] == NULL)
            rad->f[1] = new trie();
        insereaza (rad->f[1], bit-1, val, poz);
    }
}

void cautare (trie *rad, int bit, int val) {
    if (bit == -1) {
        pozs = rad->poz;
        return;
    }
    int beat = ( (val >> bit) & 1 );
    if (rad->f[1-beat] != 0) {
        cautare (rad->f[1-beat], bit-1, val);
    }
    else {
        cautare (rad->f[beat], bit-1, val);
    }

}

int main(){
    fin >> n;
    sol = -1;
    for (int i=1; i<=n; i++){
        fin >> x;
        if (i == 1) {
            s[i] = x;
        }
        else{
            s[i] = (x ^ s[i-1]);
            maxim = max (maxim, x);
        }
    }
    while (maxim){
        nr++;
        maxim /= 2;
    }
    rad = new trie();
    insereaza (rad, nr, 0, 0);
    for (int i=1; i<=n; i++){
        cautare (rad, nr, s[i]);
        if ((s[pozs] ^ s[i]) > sol){
            sol = (s[pozs] ^ s[i]);
            st = pozs + 1, dr = i;
        }
        insereaza (rad, nr, s[i], i);
    }
    fout << sol << " " << st << " " << dr;
    return 0;
}