Cod sursa(job #2095419)

Utilizator CammieCamelia Lazar Cammie Data 27 decembrie 2017 15:24:29
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

#define MAXN (1 << 21) - 1
#define inf 0x3f3f3f3f

using namespace std;

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

struct trie{
    trie *fiu[MAXN];
};

trie *root = new trie();

unsigned int v[100005], inceput, sf = 100005, in = 100005 + 1, n;
unsigned int maxim = 0;

inline void Add(trie* node, unsigned int j, unsigned int val) {
    if (j > n) {
        return;
    }
    unsigned int delta = v[j] ^ val;

    if (node->fiu[delta] == NULL){
        node->fiu[delta] = new trie();
    }

    if (delta > maxim) {
        maxim = delta;
        sf = j;
        in = inceput;
    }
    else if (delta == maxim) {
        if (in > inceput) {
            in = inceput;
            sf = j;
        }
        else if (in == inceput) {
            sf = j;
        }
    }

    Add(node->fiu[delta], j + 1, delta);
}

inline void Read() {
    fin >> n;

    for (unsigned int i = 1; i <= n; i++) {
        fin >> v[i];
    }

     for (unsigned int i = 1; i <= n; i++) {
        if (v[i] > maxim) {
            maxim = v[i];
            in = i;
            sf = i;
        }
        inceput = i;
        Add(root, i + 1, v[i]);
    }

    fout << maxim <<" " <<  in <<" " << sf;
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}