Cod sursa(job #3217668)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 24 martie 2024 11:21:10
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <stdint.h>

const int32_t MAX_N = 100000;
const int32_t MAX_VAL_LOG_2 = 21;
const int32_t MAX_VAL = 1 << MAX_VAL_LOG_2;

struct Node {
    int32_t ind;
    Node* children[2];
};

int32_t vec[MAX_N + 1];
Node nodes[MAX_VAL];
int32_t top = 0;
Node* tree;

int32_t Find(int32_t val) {
    Node* node = tree;

    for(int32_t i = MAX_VAL_LOG_2 - 1; i != -1; --i) {
        int32_t bit = (val >> i) & 1;
        int32_t child = bit ^ 1;
        if(!node->children[child])
            child ^= 1;
        
        node = node->children[child];
    }

    return node->ind;
}
void Insert(int32_t val, int32_t ind) {
    Node* node = tree;

    for(int32_t i = MAX_VAL_LOG_2 - 1; i != -1; --i) {
        int32_t bit = (val >> i) & 1;
        if(!node->children[bit]) {
            Node* newNode = nodes + top;
            ++top;
            node->children[bit] = newNode;
        }

        node = node->children[bit];
    }

    node->ind = ind;
}

int main() {
    std::ifstream fin("xormax.in");
    std::ofstream fout("xormax.out");

    int32_t n;
    fin >> n;
    for(int32_t i = 1; i <= n; ++i)
        fin >> vec[i];
    for(int32_t i = 2; i <= n; ++i)
        vec[i] ^= vec[i - 1];
    
    tree = nodes;
    ++top;

    Insert(0, 0);
    Insert(vec[1], 1);
    int32_t st = 1, dr = 1, max = vec[1];
    for(int32_t i = 2; i <= n; ++i) {
        int32_t start = Find(vec[i]);
        int32_t val = vec[i] ^ vec[start];

        if(val > max) {
            st = start + 1;
            dr = i;
            max = val;
        }

        Insert(vec[i], i);
    }

    fout << max << ' ' << st << ' ' << dr;

    fin.close();
    fout.close();

    return 0;
}