Cod sursa(job #1255986)

Utilizator tavonSuleyman Magnificul tavon Data 5 noiembrie 2014 17:45:17
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
//#define in cin
//#define out cout
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define DOWNFOR(i, a, b) for(int i = a; i >= b; --i)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define ll long long
using namespace std;
const int Nmax = 100001;
const int Mmax = 6001;
int v[Nmax];
int N,K,M;
struct big_trie{
    struct trie{
        int son[2];
        vector<int> vals;
    } T[32*Nmax];
    int K;
    int next(int w,int p){
        if(T[w].son[p]) return T[w].son[p];
        return -1;
    }
    int getnext(int w,int p){
        if(T[w].son[p]) return T[w].son[p];
        return T[w].son[p]=++K;
    }
    void push(int x,int ind){
        int w=0;
        for(int k=30;k>=0;k--){
            w=getnext(w,(x&(1<<k))>0);
            T[w].vals.push_back(ind);
        }
    }
    int search(int w,int st,int dr){
        if(w==-1) return 0;
        int i=-1,pas=(1<<15);
        int sz=T[w].vals.size();
        while(pas){
            if(i+pas<sz && T[w].vals[i+pas] < st) i+=pas;
            pas>>=1;
        }
        if(i+1<sz && T[w].vals[i+1]<=dr) return 1;
        return 0;
    }
    int query(int x,int st,int dr){
        int w=0,ans=0;
        for(int k=30;k>=0;k--){
            if( search( next(w, !( (x&(1<<k))>0 ) ) ,st,dr) ){
                ans^=(1<<k);
                w=next(w, !( (x&(1<<k))>0 ) );
            }
            else w=next(w,(x&(1<<k))>0);
        }
        return ans;
    }
    void rsort(){
        for(int i=1;i<=K;i++) sort(T[i].vals.begin(),T[i].vals.end());
    }
} BT;
struct small_trie{
    struct trie{
        int son[2];
    } T[32*Nmax];
    int K;
    int next(int w,int p){
        if(T[w].son[p]) return T[w].son[p];
        return -1;
    }
    int getnext(int w,int p){
        if(T[w].son[p]) return T[w].son[p];
        return T[w].son[p]=++K;
    }
    void push(int x,int ind){
        int w=0;
        for(int k=30;k>=0;k--){
            w=getnext(w,(x&(1<<k))>0);
        }
    }
} ST;
int main(){
    //#ifndef ONLINE_JUDGE
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    //#endif
    in>>N;//>>M;
    BT.push(0,0);
    for(int i=1;i<=N;i++){
        in>>v[i];
        v[i]^=v[i-1];
        BT.push(v[i],i);
    }
    int mx=0,pos,y;
    for(int i=1;i<=N;i++){
        int an=BT.query(v[i],0,i-1);
        if( an>mx ) mx=an,pos=i;
    }
    for(int i=0;i<pos;i++){
        if(v[i]^v[pos]==mx) y=i;
    }
    out<<mx<<' '<<y+1<<' '<<pos<<'\n';
    return 0;
}