Cod sursa(job #3135110)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 iunie 2023 20:42:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;

const int dim=1<<17;
char next_ch()
{
    static int bp=dim;
    static char buff[dim];
    if(bp==dim)
    {
        fread(buff,1,dim,stdin);
        bp=0;
    }
    return buff[bp++];
}
void get(int &a)
{
    a=0;
    char ch;
    do{
        ch=next_ch();
    }while(ch<'0'||'9'<ch);
    do{
        a=a*10+ch-'0';
        ch=next_ch();
    }while('0'<=ch&&ch<='9');
}

int sor[100001];
map <int, int> mp[21];

struct Trie{
    int last, nivel = 21;
    int zero = 0, unu = 0;
};

Trie vec[2000001];

int root = 0, cnt = 0;

void baga(int nod, int poz)
{
    vec[nod].last = poz;
    if(vec[nod].nivel == 0)
        return;
    if((1 << (vec[nod].nivel - 1)) & sor[poz])
    {
        if(vec[nod].unu == 0)
        {
            vec[nod].unu = ++cnt;
            vec[cnt].nivel = vec[nod].nivel - 1;
        }
        baga(vec[nod].unu, poz);
    }
    else
    {
        if(vec[nod].zero == 0)
        {
            vec[nod].zero = ++cnt;
            vec[cnt].nivel = vec[nod].nivel - 1;
        }
        baga(vec[nod].zero, poz);
    }
}

int p;

int cauta(int nod, int poz)
{
    if(vec[nod].nivel == 0)
    {
        p = vec[nod].last;
        return 0;
    }
    if((1 << (vec[nod].nivel - 1)) & sor[poz])
    {
        if(vec[nod].zero != 0)
            return (1 << (vec[nod].nivel - 1)) + cauta(vec[nod].zero, poz);
        else
            return cauta(vec[nod].unu, poz);
    }
    else
    {
        if(vec[nod].unu != 0)
            return (1 << (vec[nod].nivel - 1)) + cauta(vec[nod].unu, poz);
        else
            return cauta(vec[nod].zero, poz);
    }
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    get(n);
    for(int i = 1; i <= n; i++)
    {
        get(x);
        sor[i] = sor[i - 1] ^ x;
    }
    baga(root, 0);
    int max1 = -1, st = -1, dr = -1;
    for(int i = 1; i <= n; i++)
    {
        x = cauta(root, i);
        if(x > max1)
        {
            max1 = x;
            st = p + 1;
            dr = i;
        }
        baga(root, i);
    }
    cout << max1 << " " << st << " " << dr;
    return 0;
}