Cod sursa(job #2093692)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 24 decembrie 2017 12:59:56
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>
using namespace std;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 1<<16) {
            sp = 0;
            fread(buff, 1, 1<<16, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[1<<16]();
        sp = (1<<16)-1;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
}f("xormax.in");
ofstream g("xormax.out");
int n,k,sol,sst,ddr;
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+(1LL<<bit));
        ok=0;
    }
    if(A>0&&b>0)
    {
        solve(bit-1,st+a,dr,St,St+A-1,cur+(1LL<<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;
}