Cod sursa(job #2660732)

Utilizator vladth11Vlad Haivas vladth11 Data 20 octombrie 2020 12:55:39
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 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 poz = ((s & (1 << k)) > 0);
        return query(node->v[poz], 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 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;
        trie.insert(xxor, cnt);
        int comp = 0;
        int pz = 0;
        int scor = 0;
        for(int i = nr_of_bits; i >= 0; i--){
            int cc = 0;
            if((xxor & (1 << i)) > 0)
                cc = 0;
            else
                cc = (1 << i);
            if(trie.find((comp | cc))){
                comp |= cc;
                //debug(i);
                scor |= (1 << i);
            }else{
                comp |= (xxor & (1 << i));
            }
        }

        //cout << comp << "\n";
        pz = trie.find(comp);
        if(scor > maxim){
            maxim = scor;
            sol = {pz + 1, cnt};
        }
    }
    cout << maxim << " ";
    cout << sol.first << " " << sol.second;
    return 0;
}