Cod sursa(job #2662809)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 24 octombrie 2020 15:45:10
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <type_traits>
#include <random>
#include <cstring>
#include <stack>
#include <stdlib.h>
#include <map>
#include <set>
using namespace std;
#define SERVER 0
const string nameFile="xormax";
ifstream in (nameFile+".in");
ofstream out(nameFile+".out");
typedef long long ll;
typedef pair <int, int> pii;
#if (SERVER)
    #define in cin
    #define out cout
#endif
const int nmax=100000;
struct TrieNode{
    TrieNode * nxt[2];
    int poz;
    TrieNode(int pp){
        nxt[0]=nxt[1]=nullptr;
        poz=pp;
    }
};
class Trie{
public:
    TrieNode * root;
    Trie(){
        root=new TrieNode(-1);
    }
    void insert(int val, int idx){
        TrieNode * ptr=root;
        for(int pp=20; pp>=0; pp--){
            TrieNode * temp=ptr->nxt[(val>>pp)&1];
            if(temp==nullptr){
                temp=new TrieNode(-1);
                ptr->nxt[(val>>pp)&1]=temp;
            }
            ptr=temp;
        }
        ptr->poz=idx;
    }
    int query(int val, int &cc){
        return queryUtil(root, val, cc, 20);
    }
private:
    int queryUtil(TrieNode * nodAct, int val, int &cc, int lev){
        if(lev==-1)
            return nodAct->poz;

        if(nodAct->nxt[((val>>lev)&1)^1]==nullptr){
            return queryUtil(nodAct->nxt[((val>>lev)&1)], val, cc, lev-1);
        }
        else {
            cc+=1<<lev;
            return queryUtil(nodAct->nxt[((val>>lev)&1)^1], val, cc, lev-1);
        }
    }
};
int n, a[nmax+2];
int maxi=-1, st, dr;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    Trie arb;
    in>>n;
    arb.insert(0, 0);
    for(int i=1; i<=n; i++)
        in>>a[i];
    for(int i=1; i<=n; i++){
        a[i]^=a[i-1];
        int cost=0;
        int ant=arb.query(a[i], cost);
        if(maxi<cost)
            maxi=cost, dr=i, st=ant+1;
        arb.insert(a[i], i);
    }
    out<<maxi<<" "<<st<<" "<<dr<<"\n";
    return 0;
}