Cod sursa(job #2660766)

Utilizator vladth11Vlad Haivas vladth11 Data 20 octombrie 2020 14:42:44
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "


using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 100001;
const ll INF = (1LL << 50);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 22;

class Trie{
    struct Node{
        int ap = 0;
        int sf = 0;
        Node* v[2];
        Node(){
            ap = sf = 0;
            for(int i = 0;i < 2;i++){
                v[i] = NULL;
            }
        }
    };
    void add(Node* &node, int s, int k, int val){
        if(node == NULL){
            node = new Node();
        }
        node->ap = val;
        if(k == -1){
            node->sf = val;
            return;
        }
        int poz = ((s & (1 << k)) > 0);
        add(node->v[poz], s, k - 1, val);
    }
    int query(Node* &node, int s, int k){
        if(node == NULL){
            return 0;
        }
        if(node->ap == 0)
            return 0;
        if(-1 == k){
            return node->ap;
        }
        int cc = ((s & (1 << k)) > 0);
        if(node->v[!cc]!=NULL && node->v[!cc]->ap != 0){
            return query(node->v[!cc], s, k - 1);
        }else{
            return query(node->v[cc], s, k - 1);
        }
    }
    Node* root;
public:
    void insert(int s, int i){
        add(root, s, nr_of_bits, i);
    }
    void erase(int s){
        add(root, s, nr_of_bits, -1);
    }
    int find(int s){
        return query(root, s, nr_of_bits);
    }
}trie;

int sum[NMAX];

int main() {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    int n, i, cnt = 0;
    pii sol;
    int xxor = 0, maxim = 0;
    cin >> n;

    while(n--){
        int x;
        cin >> x;
        cnt++;
        xxor ^= x;
        sum[cnt] = xxor;
        trie.insert(xxor, cnt);
        int val = trie.find((xxor ^ (1 << (nr_of_bits + 1) - 1)));
        if(val == 0)
            continue;        int scor = (sum[val] ^ sum[cnt]);
        //cout << comp << "\n";
        if(scor > maxim){
            maxim = scor;
            sol = {val + 1, cnt};
        }
    }
    cout << maxim << " ";
    cout << sol.first << " " << sol.second;
    return 0;
}