Cod sursa(job #848667)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 5 ianuarie 2013 18:02:46
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <string>
#include <cstring>
#include <vector>


using namespace std;

struct trie{
    trie *sons[2];
    vector <int> ind;
    trie(){
        memset(sons,0,sizeof(sons));
    }
};

trie *root = new trie;
int mx,ind1,ind2,v[100001], xloc[100001],crit;

void trad(trie *tra, vector<int>v, int it) {
    if (it==v.size())
        tra->ind.push_back(crit);
    else {
        if (tra->sons[v[it]] == 0)
            tra->sons[v[it]] = new trie;
        trad(tra->sons[v[it]],v,it+1);
    }
}

void bitty(int x) {
    vector <int> v;
    vector <int> w;
    int i;

    while (x) {
        v.push_back(x%2);
        x/=2;
    }

    for (i=1;i<=(20-v.size()); i++)
        w.push_back(0);

    for (i=v.size()-1; i>=0; i--)
        w.push_back(v[i]);

    trad(root, w, 0);

}

int xar(trie *tra, vector <int> v, int it) {
    if (it==v.size())
        return tra->ind[0];
    else {
        if (tra->sons[v[it]])
            return xar(tra->sons[v[it]],v,it+1);
        else
            return xar(tra->sons[!v[it]],v,it+1);
    }

}

void sear(int x) {
    vector <int> v;
    vector <int> w;
    int i;

    while (x) {
        v.push_back(!(x%2));
        x/=2;
    }

    for (i=1; i<=(20-v.size()); i++)
        w.push_back(1);

    for (i=v.size()-1; i>=0; i--)
        w.push_back(v[i]);

    int l = xar(root,w,0);

    if (xloc[crit]^xloc[l]>mx) {
        mx = xloc[crit]^xloc[l];
        ind1 = l+1;
        ind2 = crit;
    }

}

int main() {
    int n,i,j,k;
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    mx = -1;
    in>>n;
    in>>v[1];
    xloc[1] = v[1];
    bitty(v[1]);
    for (i=2; i<=n; i++) {
        in>>v[i];
        xloc[i]=xloc[i-1]^v[i];

        crit = i;
        sear(xloc[i]);

        bitty(xloc[i]);

    }

    out<<mx<<' '<<ind1<<' '<<ind2<<'\n';
    out.close();
    return 0;
}