Cod sursa(job #501918)

Utilizator goguGogu Marian gogu Data 17 noiembrie 2010 01:24:04
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <cstdlib>
#include <string>
#include <set>
#define pow(x) (1<<(x))
#define Max ((1<<21)-1)
#define Dim 4000

using namespace std;

#define am(x) (ok[(x)/32] & pow((x)&31))
#define set(x) ok[x/32] |= pow(x&31)
#define cit(x) x=0; while (lin[poz]>='0'){x=10*x+lin[poz++]-'0';     \
        if (poz==Dim) fread(lin, 1, Dim, stdin), poz=0; }            \
        poz++; if (poz==Dim) fread(lin, 1, Dim, stdin), poz=0;

int n, a[100100];
unsigned ok[1<<16];
char bun[1<<21];

void finale(int i, int best){
    for (int j=i-1; j>=0; j--)
       if ((a[j]^a[i]) == best){
          printf("%d %d %d\n", best, j+1, i);
          exit(0);
       }
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d\n", &n); n++;
    char lin[Dim+10];
    fread(lin, 1, Dim, stdin);
    int i, j, poz=0, pow=0;
    ok[0]=1;
    for (i=1; i<n; set(a[i]), ++i){
        cit(j); a[i]=a[i-1]^j;
        pow |= a[i];
        if (am(Max-a[i]))
            finale(i, Max);

    }
    bun[0]=1;
    for (i=0; i<n; bun[a[i]]=1, ++i)
        if (bun[pow-a[i]])
           for (j=i-1; j>=0; j--)
               if ((a[j]^a[i])==pow)
                    finale(i, pow);
    int best=-1, p=0, u=0;
    set<int> val;
    set<int>::iterator it;
    val.insert(0);
    for (i=1; i<n; i++){
        it = val.lower_bound(pow ^ a[i]);
        if (it != val.end() && (*it ^ a[i]) > best){
            best = *it ^ a[i];
            u = i;
        }
        if (it != val.begin() && (*(--it) ^ a[i]) > best){
            best = *it ^ a[i];
            u = i;
        }
        val.insert(a[i]);
    }
    finale(u, best);
    return 0;
}