Cod sursa(job #2142271)

Utilizator catalinlupCatalin Lupau catalinlup Data 24 februarie 2018 21:33:20
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <bits/stdc++.h>
#define INFILE "xormax.in"
#define OUTFILE "xormax.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
map<int,string> BinaryVersion;
map<string,int> IntVersion;
map<int,int> Index;
vector<int> nums;
int N;
struct Nod{
    Nod*fiu[2]={nullptr,nullptr};
};
struct Trie{
    Nod *rad;
    Trie(){
        rad=new Nod;
    }
    void Insert(int val){
        string cod=BinaryVersion[val];
        Nod *q=rad;
        for(int i=0;i<cod.size();i++){
            char c=cod[i];
            if(q->fiu[c-'0']==nullptr){
                q->fiu[c-'0']=new Nod;
            }
            q=q->fiu[c-'0'];
        }
    }
    int Retrieve(int val){
        string cod=BinaryVersion[val];
        Nod*q=rad;
        string rasp="";
        for(int i=0;i<cod.size();i++){
            char c='1';
            if(cod[i]=='1')
                c='0';
            if(q->fiu[c-'0']!=nullptr){
                q=q->fiu[c-'0'];
                rasp+=c;
            }
            else if(q->fiu[cod[i]-'0']!=nullptr){
                q=q->fiu[cod[i]-'0'];
                rasp+=cod[i];
            }
            else{
                cout<<val<<" "<<i<<"\n";
                cerr<<"Eroare\n";
                return -1;
            }
        }
        return IntVersion[rasp];
    }
};
string ConvertToBinary(int num){
    string rasp="";
    while(num>0){
        int val=num%2;
        num/=2;
        char cif=(char)val+'0';
        rasp+=cif;
    }
    while(rasp.size()<20)
        rasp+="0";
    reverse(rasp.begin(),rasp.end());
    return rasp;
}
void Setup(int i){
    string BinFormat=ConvertToBinary(nums[i]);
    //cout<<BinFormat<<endl;
    BinaryVersion[nums[i]]=BinFormat;
    Index[nums[i]]=i;
    IntVersion[BinFormat]=nums[i];
}
void Read(){
    in>>N;
    nums.push_back(0);
    for(int i=1;i<=N;i++){
        int x;
        in>>x;
        nums.push_back(x);
    }
    Setup(0);
    for(int j=1;j<=N;j++){
        nums[j]=nums[j]^nums[j-1];
        Setup(j);
    }
}
void Determinare(){
    int start=0,stop=0,Max=INT_MIN;
    for(int j=1;j<=N;j++){
        Trie tr;
        string s=BinaryVersion[nums[j]];
        for(int i=1;i<=j;i++){
            string s1=BinaryVersion[nums[i-1]];
            tr.Insert(nums[i-1]);
        }
       int mx=tr.Retrieve(nums[j]);
        int val=nums[j]^mx;
        //cout<<val<<endl;
        if(val>Max){
            start=Index[mx]+1;
            stop=j;
            Max=val;
        }
    }
    out<<Max<<" "<<start<<" "<<stop<<" "<<"\n";
}

int main()
{
    Read();
    Determinare();
    return 0;
}