Cod sursa(job #2938920)

Utilizator ArianaVaidaAriana Laura Vaida ArianaVaida Data 12 noiembrie 2022 19:24:34
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#define MAX_N 100000
#include <iostream>
#include <fstream>

using namespace std;

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

int n, a[MAX_N + 1], startmax, stopmax;
struct node{
node *left = nullptr, *right = nullptr;
int index = 0;
} *root = new node();

void add(int ind){
    node* crt = root;
    for (int i = 21; i >= 0; --i)
    {
        if ((a[ind] >> i) & 1) {
            if (crt->right == nullptr)
                crt->right = new node();
            crt = crt->right;
        }
        else {
            if (crt->left == nullptr)
                crt->left = new node();
            crt = crt->left;
        }
    }
    crt->index = ind;
}

int find(int nr){
    node* crt = root;
    for (int i = 21; i >= 0; --i)
    {
        if ((nr >> i) & 1) {
            if (crt->left != nullptr)
                crt = crt->left;
            else
                crt = crt->right;
        }
        else
        {
            if (crt->right != nullptr)
                crt = crt->right;
            else
                crt = crt->left;
        }
    }
    return crt->index;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> a[i];
        a[i] ^= a[i-1];
    }
    add(0);

    for (int stop = 1; stop <= n; ++stop)
    {
        int start = find(a[stop]) + 1;
        if ((a[start - 1] ^ a[stop]) > (a[startmax - 1] ^ a[stopmax]))
        {
            startmax = start;
            stopmax = stop;
        }
        add(stop);
    }
    fout << (a[startmax - 1] ^ a[stopmax]) << " " << startmax << " " << stopmax;
    return 0;
}