Cod sursa(job #2744862)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 25 aprilie 2021 13:41:49
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define nozerous(x) (x & -x)
#define MOD 30103
#define M_PI           3.14159265358979323846
#define EPS 0.0001
using namespace std;

const int INF = (1 << 30), NMAX(100005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;
using ll = long long;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
};
int v[NMAX];
class Trie{
private:
    int indx;
    Trie *sons[2];
public:
    Trie(){
        indx = -1;
        memset(sons, 0, sizeof(sons));
    }
    void Add(int bit, int ind){
        if(bit == 0){
            indx = ind;
            return;
        }
        int need = (((1 << bit) & v[ind]) != 0);
        if(!sons[need])
            sons[need] = new Trie;
        sons[need]->Add(bit - 1, ind);
    }
    int Query(int bit, int ind){
        if(bit == 0)
            return indx;
        int need = (((1 << bit) & v[ind]) != 0);
        if(sons[1 - need])
            return sons[1 - need]->Query(bit - 1, ind);
        return sons[need]->Query(bit - 1, ind);
    }
};
Trie *root = new Trie;

int main()
{
    BUNA("xormax");
    int n;
    cin >> n;

    root->Add(20, 0);
    int maxx = 0, st = 1, dr = 1;
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        v[i] ^= v[i - 1];
        int pz = root->Query(20, i);

        if((v[i] ^ v[pz]) > maxx){
            maxx = v[i] ^ v[pz];
            st = pz + 1;
            dr = i;
        }
        root->Add(20, i);
    }
    cout << maxx << ' ' << st << ' ' << dr << '\n';
    PA();
}