Cod sursa(job #2578275)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 10 martie 2020 20:01:50
Problema Xor Max Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct Triple {
    int x, y, z;
    Triple(int x = 0, int y = 0, int z = 0) :
        x(x), y(y), z(z) { }
    inline bool operator<(const Triple& t) const {
        return x < t.x || (x == t.x && (z > t.z || (z == t.z && y < t.y)));
    }
};

class Trie {
  private:
    struct Node {
        int pos = 0;
        int next[2] = {-1, -1};
    };
    vector<Node> trie{1};

  public:
    void insert(int pos, int val) {
        int node = 0;
        for (int bit = 21; bit >= 0; bit--) {
            bool now = (val & (1 << bit));
            if (trie[node].next[now] == -1) {
                trie[node].next[now] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[now];
        }
        trie[node].pos = pos;
    }

    Triple query(int pos, int val) {
        int node = 0, ans = 0;
        for (int bit = 21; bit >= 0; bit--) {
            bool now = (val & (1 << bit));
            if (trie[node].next[!now] == -1)
                node = trie[node].next[now];
            else {
                node = trie[node].next[!now];
                ans |= (1 << bit);
            }
        }
        return Triple(ans, trie[node].pos + 1, pos);
    }
};

int main() {
    Trie trie; trie.insert(0, 0);
    int n; fin >> n; Triple ans;
    for (int i = 1, sum = 0; i <= n; i++) {
        int x; fin >> x;
        ans = max(ans, trie.query(i, x));
        trie.insert(i, sum ^= x);
    }
    fout << ans.x << ' ' << ans.y << ' ' << ans.z << '\n';

    fout.close();
    return 0;
}