Pagini recente » Cod sursa (job #650282) | Borderou de evaluare (job #2935991) | Monitorul de evaluare | Cod sursa (job #2461955) | Cod sursa (job #3317800)
//https://infoarena.ro/problema/xormax
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
//#include <vector>
#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <utility>
#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NRMAX = 100000;
const int NRCIF = 30;
int v[NRMAX + 5];
struct Nod
{
int nrc, nrcd, ind;
Nod* ch[2];
Nod() : nrc{ 0 }, nrcd{ 0 }, ind{ 0 }, ch {} {};
};
void backtr_insert(Nod* nod, char* c, int ind)
{
nod->nrcd += 1;
if (*c != '\0')
{
int nr = *c - '0';
if (!nod->ch[nr])
nod->ch[nr] = new Nod();
//cout << nr << " " << nod->nrc << " " << nod->nrcd << "\n";
backtr_insert(nod->ch[nr], c + 1, ind);
}
else
{
nod->nrc += 1;
nod->ind = ind;
}
}
int backtr_rezolvare(Nod* nod, char* c)
{
//cout << *c << "c ";
if (*c != '\0')
{
int nr = *c - '0';
int invnr = nr ^ 1;
//cout << nr << " " << nod->nrc << " " << nod->nrcd << " " << nod->ind << "\n";
if (nod->ch[invnr])
return backtr_rezolvare(nod->ch[invnr], c + 1);
else
return backtr_rezolvare(nod->ch[nr], c + 1);
}
else
{
return nod->ind;
}
}
void insert(Nod* nod, int x, int ind)
{
int j, masca;
char ch[NRCIF + 5];
memset(ch, 0, sizeof ch);
j = 1;
if (x == 0)
{
ch[1] = '0';
++j;
}
else
{
for (masca = 1; masca < (1 << NRCIF); masca <<= 1, ++j)
{
if (x & masca)
ch[j] = '1';
else
ch[j] = '0';
}
reverse(ch + 1, ch + j);
}
--j;
//for(int it = 1; it <= j; ++it)
// cout<<ch[it]<<" ";
backtr_insert(nod, ch + 1, ind);
}
int rezolvare(Nod* nod, int x)
{
int j, masca;
char ch[NRCIF + 5];
memset(ch, 0, sizeof ch);
j = 1;
if (x == 0)
{
ch[1] = '0';
++j;
}
else
{
for (masca = 1; masca < (1 << NRCIF); masca <<= 1, ++j)
{
if (x & masca)
ch[j] = '1';
else
ch[j] = '0';
}
reverse(ch + 1, ch + j);
}
--j;
//for(int it = 1; it <= j; ++it)
// cout<<ch[it]<<" ";
//cout << "\n";
return backtr_rezolvare(nod, ch + 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Nod* rad = new Nod();
int n, x, ix, i;
int rez, st = 1, dr = 1;
insert(rad, 0, 0);
fin >> n;
for (i = 1; i <= n; ++i)
{
fin >> x;
if (i == 1)
ix = x;
else
ix ^= x;
//cout << ix << " ";
v[i] = ix;
insert(rad, ix, i); // trebuie si pozitia (i)
if (i == 1)
{
rez = ix;
continue;
}
int nr = rezolvare(rad, ix);
//cout << nr << " ";
if (nr)
{
if ((v[i] ^ v[nr]) > rez)
{
rez = v[i] ^ v[nr];
st = nr + 1;
dr = i;
}
}
//cout << "\n";
}
fout << rez << " " << st << " " << dr;
return 0;
}
// Facem xor intre toate numerele pe rand.
// La fiecare adaugam in trie, pe biti numarul. Trebuie sa facem si un vector ce contine fiecare nod
// Dupa aceia trebuie sa gasim un numar j<i a.i. xorul sa fie maxim (atunci cand exista pt fiecare 0 un 1 si pt fiecare 1 un 0, alfel punem ce e).
// insert ()
// scriu numarul in binar
// luam numerele pe rand numerele
// xi^=x;
// v[i]=xi;
// insert(xi)
// rezolvare(xi)
// daca am gasit un numar astfel incat sa se respecte cerintele vedem daca v[i]^v[j] > rez
// rez=v[i]^v[j]; st=j+1; dr=i;
// fout