Cod sursa(job #2093713)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 24 decembrie 2017 13:16:53
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,k,sol=-1,sst=1,ddr=1;
pair <int,int> v[1<<17];
void solve(int bit,int st,int dr,int St,int Dr,int cur)
{
    if(bit==-1)
    {
        int a=v[st].second;
        int b=v[St].second;
        if(b<a) swap(a,b);
        if(sol<cur)
        {
            sol=cur;
            sst=a+1;
            ddr=b;
        }
        else if(sol==cur)
        {
            if(ddr>b)
            {
                sst=a+1;
                ddr=b;
            }
            else if(ddr==b&&sst<a+1) sst=a+1;
        }
        return ;
    }
    int a=0,b=0,A=0,B=0;
    for(int i=st;i<=dr;++i)
        if(v[i].first&(1<<bit)) b++;
        else a++;
    for(int i=St;i<=Dr;++i)
        if(v[i].first&(1<<bit)) B++;
        else A++;
    bool ok=1;
    if(a>0&&B>0)
    {
        solve(bit-1,st,st+a-1,St+A,Dr,cur+(1<<bit));
        ok=0;
    }
    if(A>0&&b>0)
    {
        solve(bit-1,st+a,dr,St,St+A-1,cur+(1<<bit));
        ok=0;
    }
    if(ok)
    {
        if(a>0&&A>0) solve(bit-1,st,st+a-1,St,St+A-1,cur);
        if(B>0&&b>0) solve(bit-1,st+a,dr,St+A,Dr,cur);
    }
}
int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>v[i].first;
        v[i].first^=v[i-1].first;
        v[i].second=i;
        if(sol<v[i].first)
        {
            sol=v[i].first;
            sst=1;
            ddr=i;
        }
    }
    sort(v+1,v+n+1);
    solve(21,1,n,1,n,0);
    g<<sol<<' '<<sst<<' '<<ddr;
    return 0;
}