Cod sursa(job #1763913)

Utilizator ade_tomiEnache Adelina ade_tomi Data 24 septembrie 2016 19:41:57
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int sol, a[100003];
vector <int> s;
struct Trie 
{
    int count;
    Trie *fii[2];
    Trie ()
    {
        count = 0;
        memset (fii, 0, sizeof(fii));
    }
};
int ind, sol_max, ind1, ind2, n;
void update (int poz, Trie *nod)
{
    if (poz == s.size())
    {
        nod -> count = ind;
        return ;
    }
    if (nod->fii[s[poz]] == 0)
    {
        nod->fii[s[poz]] = new Trie;
    }
    update (poz + 1, nod->fii[s[poz]]);
}
int query (int poz,  Trie *nod)
{
    if ( poz == s.size())
        return nod->count;
    int p = 1 ^ s[poz];
    if (nod -> fii[p] != 0)
        return query (poz + 1, nod->fii[p]);
    else
        
        return query (poz + 1, nod -> fii[s[poz]]);
}
Trie *T = new Trie;

int main ()
{
    ifstream cin ("xormax.in");
    ofstream cout ("xormax.out");
    cin >> n;
    for (int i = 1; i <22 ;i ++)
        s.push_back(0);
    update(0,T);

    for (int i = 1; i <= n; i++)
    {
        ind ++;
        s.clear();
        cin >> a[i];
        a[i] ^= a[i - 1];
        int aux = a[i];
        int debug = 0;
        while (aux)
        {
            s.push_back(aux % 2);
            aux /= 2;
        }
        for (int i = s.size(); i < 20;i ++)
            s.push_back(0);
        int db_dump = 0;
        if (db_dump == 1)
            cout << "here " << endl;
        reverse (s.begin(),s.end());
        if (debug)
        {
            cout << "Baza 2 a lui " << a[i] << " ";
            for (int ii = 0; ii < s.size(); ii++)
                cout << s[ii];
            cout << endl;
        }
        int j = query (0, T);
        if (db_dump == 1)
            cout << "QUERY"<<endl;
        sol = a[j] ^ a[i];
        if (sol > sol_max)
        {
            ind1 = j;
            ind2 = i;
            sol_max = sol;
        }
        else 
        if (sol == sol_max && i - j < ind2 - ind1)
        {
            ind1 = j;
            ind2 = i;
        }
        update (0, T);
        s.clear();

    }
    cout << ( a[ind2] ^ a[ind1]) << " " << ind1 + 1 <<  " " << ind2 << "\n";
    return 0;
}