Cod sursa(job #2006845)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 31 iulie 2017 22:59:27
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
class trie{
    public:
    int inf;
    trie *son[2];
    trie() {
        inf = 0;
        for(int i = 0;i < 2;i++)
            son[i] = NULL;
    }
    void add(int x, int bit, int poz){
        int extr;
        if(bit == -1)  {
            if(poz > inf)
                inf = poz;
        }
        else  {
            extr = (x & (1 << bit)) > 0;
            if(son[extr] == NULL)
                son[extr] = new trie;
            son[extr] -> add(x, bit - 1, poz);
        }
    }
};
FILE *fin, *fout;
int main()  {
    fin = fopen("xormax.in", "r");
    fout = fopen("xormax.out", "w");
    int n, max, st, dr, extr, bst;
    trie *t, *cursor;
    t = new trie;
    t -> add(0, 20, 1);
    int s = 0;
    max = -1, st = -1, dr = -1;
    fscanf(fin, "%d", &n);
    for(int i = 1;i <= n;i++)  {
        int x;
        fscanf(fin, "%d", &x);
        s = s ^ x;
        cursor = t;
        bst = 0;
        for(int j = 20;j >= 0;j--)  {
            extr = (s & (1 << j)) > 0;
            if(cursor -> son[1 - extr] != NULL)  {
                bst = (bst << 1) | 1;
                cursor = cursor -> son[1 - extr];
            }
            else {
                bst = bst << 1;
                cursor = cursor -> son[extr];
            }
        }
        if(max < bst)
            max = bst, dr = i, st = cursor -> inf;
        t -> add(s, 20, i + 1);
    }
    fprintf(fout, "%d %d %d", max, st, dr);
    fclose(fin);
    fclose(fout);
    return 0;
}