Cod sursa(job #3203351)

Utilizator poparobertpoparobert poparobert Data 13 februarie 2024 15:47:17
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <fstream>
#include <cstdio>
#include <utility>
#include <numeric>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
typedef long long ll;
typedef pair<ll,ll> pll;
ll ax;
pll rez;
class trie{
  public:
  ll poz=0;
  trie*next[2]={};
  void insert(const ll &s,ll pz=0,ll p=22){
    if(p<0)return poz=max(poz,pz),void();
    ll ax=(s&(1ll<<p))?1:0;
    if(!next[ax])next[ax]=new trie;
    next[ax]->insert(s,pz,p-1);
  }
  pll xormax(ll tg=0,ll p=22){
    if(p<0)return pll(0,poz);
    ll ax=(tg&(1ll<<p))?0:1;
    if(!next[ax]){
      ax=1-ax;
      pll rez=next[ax]->xormax(tg,p-1);
      rez.first+=ax*(1ll<<p);
      return rez;
    }
    pll rez=next[ax]->xormax(tg,p-1);
    rez.first+=ax*(1ll<<p);
    return rez;
  }
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m,i,j,k,l,rez=0,st,dr,x,pref=0;
  fin>>n;
  trie tr;
  tr.insert(0,0);
  for(i=1;i<=n;i++){
    fin>>x;
    pref^=x;
    pll ax=tr.xormax(pref);
    ax.first^=pref;
    if(ax.first>=rez)rez=ax.first,st=ax.second,dr=i;
    tr.insert(pref,i);
  }
  fout<<rez<<' '<<st+1<<' '<<dr;
  return 0;
}