Cod sursa(job #2968085)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 20 ianuarie 2023 18:03:23
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

struct Trie_Nod
{
    int nrc;
    Trie_Nod* fii[2];

    Trie_Nod()
    {
        nrc = 0;
        for (int i = 0; i < 2; i++)
            fii[i] = NULL;
    }
};

Trie_Nod* root = new Trie_Nod;

int n,sp[100005],a[100005];
int maxim,st,dr;

void update(int x)
{
    int bits[25];
    for (int i = 20; i >= 0; i--)
    {
        bits[i] = x % 2;
        x /= 2;
    }
    Trie_Nod* nod = root;
    root->nrc++;
    for (int i = 0; i <= 20; i++)
    {
        int p = bits[i];
        if (nod->fii[p] == NULL)
            nod->fii[p] = new Trie_Nod;
        nod = nod->fii[p];
        nod->nrc++;
    }
}

void query(int x,int poz)
{
    int bits[25];
    for (int i = 20; i >= 0; i--)
    {
        bits[i] = x % 2;
        x /= 2;
    }
    Trie_Nod* nod = root;
    int ans = 0;
    for (int i = 0; i <= 20; i++)
    {
        ans *= 2;
        int p = 1 - bits[i];
        if (nod->fii[p] == NULL or nod->fii[p]->nrc == 0)
        {
            p = 1 - p;
            nod = nod->fii[p];
        }
        else
        {
            ans++;
            nod = nod->fii[p];
        }
    }
    if (ans > maxim)
    {
        dr = poz;
        maxim = ans;
    }
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> a[i];
    for (int i = 1; i <= n; i++)
        sp[i] = sp[i - 1] ^ a[i];
    update(0);
    for (int i = 1; i <= n; i++)
    {
        update(sp[i]);
        query(sp[i],i);
    }
    if (maxim == 0)
    {
        out << 0 << ' ' << 1 << ' ' << 1;
        return 0;
    }
    out << maxim << ' ';
    int xr = 0;
    for (int i = dr; i >= 1; i--)
    {
        xr ^= a[i];
        if (xr == maxim)
        {
            st = i;
            break;
        }
    }
    out << st << ' ' << dr;
    return 0;
}