Cod sursa(job #2570908)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 4 martie 2020 19:56:06
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>

using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
//----------------------------------------
///Globale
int n,st,dr,rasp,d[1000001];
struct trie
{
    trie *z,*u;
    int who;
    trie()
    {
        z = NULL;
        u = NULL;
    }
}*r;
//----------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//----------------------------------------
int main()
{
    citire();
    rezolvare();
    afisare();
}
//----------------------------------------
void afisare()
{
    g << rasp << " " << st << " " << dr;
}
//----------------------------------------
int cauta(int val,int bit,trie *nod)
{
    if(bit == -1)
        return nod -> who;
    int x = val & (1 << bit);
    if(x == 0)
    {
        if(nod -> u != NULL)
            return cauta(val,bit - 1,nod -> u);
        else
            return cauta(val,bit - 1,nod -> z);
    }
    else
    {
        if (nod -> z != NULL)
            return cauta(val,bit - 1,nod -> z);
        else
            return cauta (val,bit - 1,nod -> u);
    }
}
//----------------------------------------
trie* adauga(int i,int bit,trie*nod)
{
    if(nod == NULL)
        nod = new trie;
    if(bit == -1)
    {
        nod -> who = i;
        return nod;
    }
    int x = d[i] & (1 << bit);
    if(x == 0)
        nod -> z = adauga(i,bit - 1,nod -> z);
    else
        nod -> u = adauga(i,bit - 1,nod -> u);
    return nod;
}
//----------------------------------------
void rezolvare()
{
    rasp = -1;
    r = adauga(0,21,r);
    for(int i = 1; i <= n; ++i)
    {
        int gasit = cauta(d[i],21,r);
        if((d[gasit] ^ d[i]) > rasp)
        {
            rasp = d[gasit] ^ d[i];
            dr = i;
            st = gasit + 1;
        }
        r = adauga(i,21,r);
    }
}
void citire()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        int x;
        f >> x;
        d[i] = d[i - 1] ^ x;
    }
}