Cod sursa(job #2565399)

Utilizator memecoinMeme Coin memecoin Data 2 martie 2020 14:07:53
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "xormax";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

class Trie {
public:
    Trie *children[2];
    int index;
    
    void insert(int bit, int x, int index) {
        if (bit == -1) {
            this->index = index;
            return;
        }
        
        bool val = (x & (1 << bit)) > 0;
        
        if (children[val] == NULL) {
            children[val] = new Trie();
        }
        
        children[val]->insert(bit - 1, x, index);
    }
    
    pair<int, int> findBest(int bit, int x) {
        if (bit == -1) {
            return {0, index};
        }
        
        bool val = (x & (1 << bit)) > 0;
        
        pair<int, int> res;
        
        if (children[!val] != NULL) {
            res = children[!val]->findBest(bit - 1, x);
            res.first += (1 << bit);
        } else {
            res = children[val]->findBest(bit - 1, x);
        }
        return res;
    }
};

Trie trie;
int maxBit = 21;
int n;

int main() {
    
    trie.insert(maxBit, 0, 0);
    
    int s = 0;
    int best = -1;
    int start = 0;
    int end = 0;
    
    fin >> n;
    
    for (int i = 0; i < n; ++i) {
        int x;
        fin >> x;
        s ^= x;
        
        auto candidate = trie.findBest(maxBit, s);
        
        if (candidate.first > best) {
            best = candidate.first;
            end = i + 1;
            start = candidate.second + 1;
        }
        
        trie.insert(maxBit, s, i + 1);
    }
    
    fout << best << " " << start << " " << end;
    
    return 0;
}