Cod sursa(job #3170290)

Utilizator tomaionutIDorando tomaionut Data 17 noiembrie 2023 11:45:21
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<bits/stdc++.h>
using namespace std;

struct Trie
{
    int poz;
    Trie *leg[2];
    Trie(int p)
    {
        poz = p;
        leg[0] = leg[1] = NULL;
    }
};
Trie *rad;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

void Adauga(int w, int ind)
{
    int i, j;
    Trie *q, *p = rad;
    for (i = 20; i >= 0; i--)
    {
        j = (w >> i) & 1;
        if (p->leg[j] != NULL) p = p->leg[j];
        else
        {
            q = new Trie(0);
            p->leg[j] = q;
            p = q;
        }
    }
    if (p->poz == 0) p->poz = ind;
}

void ValMax(int w, int &M, int &P)
{
    int i, j;
    Trie *p = rad;
    M = 0;
    for (i = 20; i >= 0; i--)
    {
        j = (w >> i) & 1;

        if (p->leg[1-j] != NULL)
        {
            M = M | (1 << i);
            p = p->leg[1 - j];
        }
        else if (p->leg[j] != NULL) p = p->leg[j];
        else {P = p->poz; return;}
    }
    P = p->poz;
}

int main()
{
    int n, i, w, x, answer = -1, st, dr, v, P;
    rad = new Trie(0);
    fin >> n;
    w = st = dr = 0;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        if (answer < x)
        {
            answer = x;
            st = dr = i;
        }
        w = w ^ x;
        if (i > 1)
        {
            ValMax(w, v, P);
            if (answer < v)
            {
                answer = v;
                st = P + 1; dr = i;
            }
        }
        Adauga(w, i);
    }
    fout << answer << " " << st << " " << dr << "\n";
    fout.close();
    return 0 ;
}