Cod sursa(job #2964124)

Utilizator lucametehauDart Monkey lucametehau Data 12 ianuarie 2023 12:38:27
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <chrono>
#include <cassert>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <random>
#include <string>
#include <complex>
#include <algorithm>
#include <numeric>
//#include <ext/pb_ds/assoc_container.hpp>

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#  define __builtin_popcountll __popcnt64
#endif

#pragma warning(disable : 4996)

#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define x first
#define y second
#define ld long double
#define ll long long
#define ull unsigned long long
#define us unsigned short
#define lsb(x) ((x) & (-(x)))
#define pii pair <int, int>
#define pll pair <ll, ll>

using namespace std;
//using namespace __gnu_pbds;

mt19937_64 gen(time(0));
uniform_int_distribution <ull> rng;

struct Node {
    Node* sons[2];
};

struct Trie {
    Node* root;

    Trie() {
        root = new Node();
    }

    void add(int x) {
        update(root, x, 20);
    }

    void update(Node*& node, int value, int b) {
        bool bit = (value >> b) & 1;

        if (!node->sons[bit])
            node->sons[bit] = new Node();

        if(b)
            update(node->sons[bit], value, b - 1);
    }

    int get_max(int value) {
        return query(root, value, 20);
    }

    int query(Node*& node, int value, int b) {
        bool bit = (value >> b) & 1;
        if (b == 0)
            return (node->sons[bit ^ 1] ? 1 : 0);
        if (node->sons[1 ^ bit])
            return (1 << b) | query(node->sons[1 ^ bit], value, b - 1);
        return query(node->sons[bit], value, b - 1);
    }
} trie;

int n, x;

int lst[(1 << 21)];

void solve() {
    cin >> n;
    int s = 0, mx = -1, l = 0, r = 0;

    trie.add(0);

    for (int i = 1; i <= n; i++) {
        cin >> x;
        s ^= x;
        int value = trie.get_max(s);
        if (value > mx) {
            mx = value;
            l = lst[value ^ s] + 1;
            r = i;
        }
        trie.add(s);
        lst[s] = i;
    }

    cout << mx << " " << l << " " << r << "\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    srand(time(0));

#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
#endif

    int T = 1;

    //cin >> T;

    for (int t = 1; t <= T; t++) {
        solve();
    }

    return 0;
}