Cod sursa(job #2655620)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 4 octombrie 2020 22:38:33
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 100005;
int n, v[nmax], ans, a, b, minim;

struct Trie{
    int pos;
    Trie *fiu[2];
    Trie(){
        pos = 0;
        fiu[0] = fiu[1] = nullptr;
    }
};

Trie *root = new Trie();

void Add(Trie *node, int nr, int i, int j){
    if (j < 0){
        node->pos = i;
        return;
    }
    int bit = (nr >> j) & 1;
    if (node->fiu[bit] == nullptr){
        node->fiu[bit] = new Trie();
        Add(node->fiu[bit], nr, i, j - 1);
    }
    else{
        Add(node->fiu[bit], nr, i, j - 1);
    }
}

int Find(Trie *node, int nr, int i){
    if (i < 0){
        return node->pos;
    }
    int bit = (nr >> i) & 1;
    if (node->fiu[1 - bit] != nullptr){
        return Find(node->fiu[1 - bit], nr, i - 1);
    }
    return Find(node->fiu[bit], nr, i - 1);
}

int main(){
    fin >> n;
    Add(root, 0, 0, 22);
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
        v[i] ^= v[i - 1];
        int pos = Find(root, v[i], 22);
        int val = (v[i] ^ v[pos]);
        if (val > ans){
            ans = val;
            a = pos;
            b = i;
            minim = i - pos;
        }
        Add(root, v[i], i, 22);
    }
    fout << ans << " " << a + 1 << " " << b << "\n";
    fin.close();
    fout.close();
    return 0;
}