Cod sursa(job #850756)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 8 ianuarie 2013 21:50:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <string>
#include <cstring>
#include <vector>


using namespace std;

struct trie{
    trie *sons[2];
    int loc;
    trie(){
        sons[0]=sons[1]=0;
    }
};

trie *root = new trie;
int xr[100001];
int tar,mx,in1,in2;

void add(trie *tri, int i) {
    if (i == -1) {
        tri->loc = tar;
    }
    else {
        if (((1<<i)|xr[tar]) == xr[tar]) {
            if (!tri->sons[1])
                tri->sons[1] = new trie;
            add(tri->sons[1],i-1);
        }
        else {
            if (!tri->sons[0])
                tri->sons[0] = new trie;
            add(tri->sons[0],i-1);
        }
    }
}

void find(trie *tri, int i) {
    if (i == -1) {
        if (((xr[tar])^(xr[tri->loc]))>mx) {
            mx = ((xr[tar])^(xr[tri->loc]));
            in1=(tri->loc)+1;
            in2=tar;
        }
    }
    else {
        if (((1<<i)|xr[tar]) == xr[tar]) {
            if (tri->sons[0])
                find(tri->sons[0],i-1);
            else
                find(tri->sons[1],i-1);
        }
        else {
            if (tri->sons[1])
                find(tri->sons[1],i-1);
            else
                find(tri->sons[0],i-1);
        }
    }
}

int main() {
    int n,i,k;
    mx=-1;
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    in>>n;
    add(root,20);
    for (i=1; i<=n; i++) {
        tar=i;
        in>>k;
        xr[i] = xr[i-1]^k;

        find(root,20);
        add(root,20);
    }

    out<<mx<<' '<<in1<<' '<<in2;
    out.close();
    return 0;
}