Cod sursa(job #3151768)

Utilizator andiRTanasescu Andrei-Rares andiR Data 22 septembrie 2023 19:48:07
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

int n, v[Nmax];
struct TRIE{
    struct NODE{
        int val;
        NODE* nxt[2]={nullptr, nullptr};
    };
    NODE* root;
    TRIE(){
        root=new NODE;
    }
    void add(int ind, int bit, NODE* crt){
        crt->val=ind;
        if (bit==-1)
            return;
        bool ok;
        int mask=(1<<bit);
        ok=(v[ind]&mask);
        if (crt->nxt[ok]==nullptr)
            crt->nxt[ok]=new NODE;
        add(ind, bit-1, crt->nxt[ok]);
    }
    NODE* querry(int nr, int bit, NODE* crt){
        if (bit==-1)
            return crt;
        bool ok;
        int mask=(nr&(1<<bit));
        ok=!(nr&mask);
        if (crt->nxt[ok]!=nullptr)
            return querry(nr, bit-1, crt->nxt[ok]);
        if (crt->nxt[!ok]!=nullptr)
            return querry(nr, bit-1, crt->nxt[!ok]);
        return crt;
    }
};
int main()
{
    fin>>n;
    for (int i=1; i<=n; i++){
        fin>>v[i];
        v[i]^=v[i-1];
    }
    TRIE trie;
    int mx=0, l, r;
    for (int i=0; i<=n; i++){
        trie.add(i, 21, trie.root);
        auto p=trie.querry(v[i], 21, trie.root);
        if ((v[i]^v[p->val])>mx){
            mx=v[i]^v[p->val];
            l=p->val+1;
            r=i;
        }
    }
    fout<<mx<<' '<<l<<' '<<r;
    return 0;
}