Cod sursa(job #2093745)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 24 decembrie 2017 13:35:41
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,k,sol=-1,sst,ddr;
pair <int,int> v[1<<17];
void check(int a,int b,int cur)
{
    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;
    }
}
void solve(int bit,int st,int dr,int St,int Dr,int cur)
{
    if(bit==-1)
    {
        for(int i=st;i<=min(dr,st+5);++i)
            for(int j=St;j<=min(Dr,St+5);++j)
                check(v[i].second,v[j].second,cur);
        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;
}