Cod sursa(job #3125082)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 1 mai 2023 19:17:39
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


#define NMAX (int)(2e5)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {cerr << '{'; __print(std::get<0>(x)); cerr << ','; __print(std::get<1>(x)); cerr << ','; __print(std::get<2>(x)); cerr << '}';}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif


ordered_set<int> st; // Policy-based DS https://codeforces.com/blog/entry/11080

struct Trie {
    Trie* zero;
    Trie* one;
    int pos;

};


int T, N;
vector<int> v;
int R = 0;
int mx = -1, start = -1, stop = -1;

void add(int x, Trie* trie, int i) {

    Trie* walk = trie;
    for (int i = 31; i >= 0; --i) {

       bool bit = ((x >> i) & 1);
       if (bit) {
           if (!walk->one)
               walk->one = new Trie();
           walk = walk->one;
       } else {
           if (!walk->zero)
               walk->zero = new Trie();
           walk = walk->zero;
       }
    }

    walk->pos = i;

    return;
}

int main() {

    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    cin >> N;
    v = vector<int>(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];


    Trie* trie = new Trie();
    add(0, trie, -1);

    for (int i = 0; i < N; ++i) {
        const int& el = v[i];
        R ^= el;
        int x = 0;

        Trie* walk = trie;
        for (int j = 31; j >= 0; --j) { // go through the bits of §x§ from MSB to LSB
            bool bit = ((el >> j) & 1);  // true, of el has bit of 1 on pos "i"

            if (bit) {
                if (walk->zero) {
                  walk = walk->zero;
                } else {
                  x |= (1 << j); // keep "1" on pos "i"
                  walk = walk->one;
                }
            }
            else {
                if (walk->one) {
                 walk = walk->one;
                 x |= (1 << j);
                } else {
                walk = walk->zero;
                }

            }

        }

        int cand = R ^ x;
        if (cand > mx) {
            mx = cand;
            start = walk->pos + 1;
            stop = i;
        }
        mx = max(mx, R ^ x);
        add(R, trie, i);

    }


    cout << mx << ' ' << start  + 1 << ' ' << stop + 1 << '\n'; // 1-indexed

    return 0;
}