Cod sursa(job #2990560)

Utilizator pctirziuTirziu Petre pctirziu Data 8 martie 2023 09:38:22
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <map>

using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int nmax = 1e5 + 5;
const int valmax = (1 << 21);
int v[nmax], f[valmax];
struct trie
{
    struct trie *biti[2];
};
struct trie *getnode()
{
    struct trie *newnode = new trie;
    newnode->biti[0] = NULL;
    newnode->biti[1] = NULL;
    return newnode;
};
struct trie *root = getnode();
int trie_search(int x)
{
    struct trie *curr = root;
    int xormaxim = 0;
    for(int i = 20; i >= 0; i--){
        if(x & (1 << i)){
            if(curr->biti[0] != NULL){
                curr = curr->biti[0];
                xormaxim += (1 << i);
            }
            else if(curr->biti[1] != NULL)
                curr = curr->biti[1];
        }
        else{
            if(curr->biti[1] != NULL){
                curr = curr->biti[1];
                xormaxim += (1 << i);
            }
            else if(curr->biti[0] != NULL)
                curr = curr->biti[0];
        }
    }
    return xormaxim;
}
void trie_insert(int x)
{
    struct trie *curr = root;
    for(int i = 20; i >= 0; i--){
        if(x & (1 << i)){
            if(curr->biti[1] == NULL)
                curr->biti[1] = getnode();
            curr = curr->biti[1];
        }
        else{
            if(curr->biti[0] == NULL)
                curr->biti[0] = getnode();
            curr = curr->biti[0];
        }
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    int maxx = v[1], curr = v[1], stanga = 1, dreapta = 1;
    f[v[1]] = 1;
    trie_insert(v[1]);
    for(int i = 2; i <= n; i++){
        curr = curr ^ v[i];
        int query = trie_search(curr);
        if(query > maxx){
            maxx = query;
            stanga = f[curr ^ query] + 1;
            dreapta = i;
        }
        if(v[i] > maxx){
            maxx = v[i];
            stanga = dreapta = i;
        }
        trie_insert(curr);
        f[curr] = i;
    }
    cout << maxx << " " << stanga << " " << dreapta;
    return 0;
}