Cod sursa(job #3245350)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 28 septembrie 2024 17:07:31
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "xormax";

std :: ifstream f(FILENAME + ".in");

std :: ofstream g(FILENAME + ".out");

const int NMAX = 1e5 + 5;

struct nod
{
    int ind = -1;

    nod * st = nullptr;

    nod * dr = nullptr;
};

int n;

int start;

int stop;

int maxi = -1;

int i;

int csor[NMAX];

int v[NMAX];

std :: string s;

void add(nod * & trie, int poz)
{
    if(poz < s.size())
    {
        if(s[poz] == '0')
        {
            if(trie -> st == nullptr)
            {
                trie -> st = new nod;
            }

            add(trie -> st, poz + 1);
        }
        else
        {
            if(trie -> dr == nullptr)
            {
                trie -> dr = new nod;
            }

            add(trie -> dr, poz + 1);
        }
    }
    else
    {
        trie -> ind = i;
    }
}

std :: string to_string(int x)
{
    std :: string aux = "";

    while(x)
    {
        if(x % 2)
        {
            aux += '1';
        }
        else
        {
            aux += '0';
        }

        x /= 2;
    }

    while(aux.size() < 21)
    {
        aux += '0';
    }

    std :: reverse(aux.begin(), aux.end());

    return aux;
}

int op(nod * trie, int poz)
{
    if(poz < s.size())
    {
        if(s[poz] == '0')
        {
            if(trie -> dr)
            {
                return op(trie -> dr, poz + 1);
            }
            else
            {
                return op(trie -> st, poz + 1);
            }
        }
        else
        {
            if(trie -> st)
            {
                return op(trie -> st, poz + 1);
            }
            else
            {
                return op(trie -> dr, poz + 1);
            }
        }
    }
    else
    {
        return trie -> ind;
    }
}

int main()
{

    f >> n;

    for(int i = 1; i <= n; i ++)
    {
        f >> v[i];
    }

    for(int i = 1; i <= 21; i ++)
    {
        s += '0';
    }

    nod * trie = new nod;

    add(trie, 0);

    for(i = 1; i <= n; i ++)
    {
        csor[i] = csor[i - 1] ^ v[i];

        s = to_string(csor[i]);

        int st = op(trie, 0);

        if((csor[i] ^ csor[st]) > maxi)
        {
            start = st;

            stop = i;

            maxi = (csor[i] ^ csor[st]);
        }

        add(trie, 0);
    }

    g << maxi << " " << start + 1 << " " << stop;

    return 0;
}