Cod sursa(job #2644392)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 24 august 2020 13:45:12
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#define NMAX 100005

using namespace std;

int n, v[NMAX], ans, l, r;

struct trie{
    trie *f[2];
    int id;

    trie(){
        f[0] = f[1] = NULL;
    }
}*T;

void add(int x, int id){
    trie *crt = T;
    for (int i=20;i>=0;i--){
        if (!crt->f[(x&(1<<i))!=0])
            crt->f[(x&(1<<i))!=0] = new trie();
        crt = crt->f[(x&(1<<i))!=0];
    }
    crt->id = id;
}

void query(int x, int id){
    trie *crt = T;
    for (int i=20;i>=0;i--){
        if (!crt->f[(x&(1<<i))==0]) crt = crt->f[((x&(1<<i)))!=0];
        else crt = crt->f[(x&(1<<i))==0];
    }
    int a = x;
    int b = v[crt->id];
    if ((a ^ b) > ans){
        ans = a ^ b;
        l = crt->id + 1;
        r = id;
    }
}

int main()
{
    cin.sync_with_stdio(false);
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    T = new trie();
    add(0,0);
    ans = -1;
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> v[i];
        v[i] ^= v[i-1];
        query(v[i], i);
        add(v[i], i);
    }

    cout << ans << ' ' << l << ' ' << r << '\n';

    return 0;
}