Cod sursa(job #3189911)

Utilizator PetraPetra Hedesiu Petra Data 6 ianuarie 2024 17:39:35
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
using namespace std;

#define MAXL 25
#define MAXN 100005
#define INF 0x3f3f3f3f
#define TEST(a, b) (((a) & (1 << b)) != 0)
#define max(a, b) (((a) > (b)) ? (a) : (b))

struct node {
    int key;
    node* next[2];

    node() {
        key = INF;
        next[0] = next[1] = NULL;
    }
};

FILE* f = fopen("xormax.in", "r");
FILE* g = fopen("xormax.out", "w");

node root;
int v[MAXN], n;

void add(int val, int pos)
{
    bool bit;
    node* nd = &root;

    for (int i = MAXL; i >= 0; --i) {
        bit = TEST(val, i);
        if (nd->next[bit] == 0) {
            nd->next[bit] = new node;
        }
        nd = nd->next[bit];
    }

    nd->key = pos;
}

int find(int val)
{
    bool bit;
    node* nd = &root;

    for (int i = MAXL; i >= 0; --i) {
        bit = TEST(val, i);
        if (nd->next[!bit] == 0) {
            nd = nd->next[bit];
        } else {
            nd = nd->next[!bit];
        }
    }

    return nd->key;
}

int main()
{
    fscanf(f, "%d\n", &n);

    for (int i = 1, t; i <= n; ++i) {
        fscanf(f, "%d ", &t);
        v[i] = v[i - 1] ^ t;
    }

    int beg = 0, end = 0, maxv = -1;
    add(0, 0);
    for (int i = 1, t; i <= n; ++i) {
        t = find(v[i]);
        if ((v[t] ^ v[i]) > maxv) {
            maxv = v[t] ^ v[i];
            end = i, beg = t;
        }
        add(v[i], i);
    }

    fprintf(g, "%d %d %d\n", maxv, beg + 1, end);

    fclose(f);
    fclose(g);
    return 0;
}