Cod sursa(job #3177334)

Utilizator paull122Paul Ion paull122 Data 28 noiembrie 2023 23:47:06
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct Nod
{
    Nod* fii[2]={NULL,NULL};
    int id=0;
};
int pos=0;
pair<int,int> query(Nod* n, int x)
{
    Nod *t = n;
    int num=0;
    for(int i=21;i>=0;i--)
    {
        int b=(x>>i)&1;
        if(t->fii[!b])
        {
            num += 1 << i;
            t=t->fii[!b];
        }
        else
        {
            t=t->fii[b];
        }
    }
    return {num,t->id};
}
void update(Nod* n,int x,int id)
{
    Nod *t=n;
    for(int i=21;i>=0;i--)
    {
        int b=(x>>i)&1;
        if(!t->fii[b])
        {
            t->fii[b]= new Nod;
        }
        t=t->fii[b];
    }
    t->id = id;
}

Nod* t = new Nod;


int n;
int a[100001];
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
    }
    int currx=a[1];
    pair<int,pair<int,int>> res = {a[1],{1,1}};
    update(t,a[1],2);
    for(int i=2;i<=n;i++)
    {
        currx ^= a[i];
        pair<int,int> val= query(t,currx);
        if(val.first > res.first)
        {
            res = {val.first,{val.second,i}};
        }
        update(t,currx,i+1);
    }
    fout << res.first << " " << res.second.first << " " << res.second.second;
}