Cod sursa(job #2476693)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 19 octombrie 2019 11:03:44
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

const int MV = 1e5 ;

FILE *in = fopen("xormax.in", "r"), *out = fopen("xormax.out", "w") ;

int v[MV + 5] ;

struct Trie {
        Trie *fii[2] ;
        int val ;
        Trie() {
                fii[0] = fii[1] = NULL ;
                val = 0 ;
        }
};

Trie *root = new Trie ;

void Insert_in_Trie(Trie *node, int number, int level, int ind) {
        if (level == 0) {
                node -> val = ind ;
                return ;
        }
        int bit((number >> level) & 1) ;
        if (node -> fii[bit] == NULL) {
                node -> fii[bit] = new Trie ;
        }
        Insert_in_Trie(node -> fii[bit], number, level - 1, ind) ;
}

int Get_answer_from_Trie(Trie *node, int number, int level) {
        if (level == 0) {
                return node -> val ;
        }
        int bit((number >> level) & 1) ;
        if (node -> fii[!bit] != NULL) {
                return Get_answer_from_Trie(node -> fii[!bit], number, level - 1) ;
        }
        return Get_answer_from_Trie(node -> fii[bit], number, level - 1) ;
}

int main() {
        int n, i ;
        fscanf(in, "%d", &n) ;
        for (i = 1 ; i <= n ; ++ i) {
                fscanf(in, "%d", v + i) ;
                v[i] ^= v[i - 1] ;
        }
        Insert_in_Trie(root, v[1], 25, 1) ;
        int max_xor(0), st(0), dr(0) ;
        int max_back ;
        for (i = 2 ; i <= n ; ++ i) {
                max_back = Get_answer_from_Trie(root, v[i], 25) ;
                if (max_xor < (v[i] ^ v[max_back])) {
                        max_xor = v[i] ^ v[max_back] ;
                        dr = i ;
                        st = max_back + 1 ;
                }
                Insert_in_Trie(root, v[i], 25, i) ;
        }
        fprintf(out, "%d %d %d", max_xor, st, dr) ;
}