Cod sursa(job #3189953)

Utilizator PetraPetra Hedesiu Petra Data 6 ianuarie 2024 18:11:15
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>

#define x first
#define poz second
#define NMAX 100002
#define INF 0x3f3f3f3f
#define TEST(a, b) (((a) & (1 << b)) != 0)

using namespace std;

FILE* fin = fopen("xormax.in", "r");
FILE* fout = fopen("xormax.out", "w");


struct trie {
    int poz;
    trie *bit[2];
    trie() {
        poz = INF;
        bit[0] = bit[1] = NULL;
    }
};

trie *T = new trie;

void add(int val, int pos)
{
    bool bit;
    trie* nd = T;

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

    nd->poz = pos;
}

int find(int val)
{
    bool bit;
    trie* nd = T;

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

    return nd->poz;
}

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

    add(0, 0);
    int mx = -1, st = 0, dr = 0;

     for (int i = 1, t; i <= n; ++i) {
        t = find(v[i]);
        if ((v[i] ^ v[t]) > mx) {
            mx = v[i] ^ v[t];
            dr = i, st = t;
        }
        add(v[i], i);
    }
    fprintf(fout, "%d %d %d\n", mx, st + 1, dr);
    return 0;
}