Cod sursa(job #2473536)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 13 octombrie 2019 19:33:40
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int nmax = 100000, lgmax = 20;

struct Trie{
    int ind;
    Trie *son[2];
    Trie(){
        memset(son, 0, sizeof son);
        ind = 0;
    }
};
Trie *trie = new Trie;

int n, v[nmax + 5], smax, l, r;

void Read(){
    fin >> n;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
        v[i] ^= v[i - 1];
    }
}

void Insert(int ind, int pos, Trie *p){
    if (pos == 0){
        p->ind = ind;
        return;
    }
    bool x = (1 << pos) & v[ind];
    if (!p->son[x])
        p->son[x] = new Trie;
    Insert(ind, pos - 1, p->son[x]);
}

int Search(int ind, int pos, Trie *p){
    if (pos == 0)
        return p->ind;
    bool x = (1 << pos) & v[ind];
    if (p->son[1 - x])
        return Search(ind, pos - 1, p->son[1 - x]);
    else
        return Search(ind, pos - 1, p->son[x]);
}

void Solve(){
    Insert(0, lgmax, trie);
    l = r = 1;
    for (int i = 1; i <= n; i++){
        int index = Search(i, lgmax, trie);
        int sum = v[i] ^ v[index];
        if (sum > smax){
            smax = sum;
            l = index + 1;
            r = i;
        }
        Insert(i, lgmax, trie);
    }
    fout << smax << ' ' << l << ' ' << r << '\n';
}

int main(){
    Read();
    Solve();
    return 0;
}