Pagini recente » Monitorul de evaluare | Istoria paginii onis-2016/clasament/runda-2 | Cod sursa (job #2278891) | Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 | Cod sursa (job #2488056)
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int number;
Node* v[2] = {nullptr, nullptr};
} *trie = new Node;
void push_trie(int x)
{
stack<bool> binary;
int copy_x = x;
for(int i = 1; i <= 22; ++i)
{
binary.push(x % 2);
x = x/2;
}
cout << copy_x <<" ";
Node* temp = trie;
while(binary.empty() == false)
{
if(temp->v[binary.top()] == nullptr)
temp->v[binary.top()] = new Node;
temp = temp->v[binary.top()];
cout << binary.top();
binary.pop();
}
cout << endl;
temp->number = copy_x;
}
int max_trie(int x)
{
stack<bool> binary;
int copy_x = x;
for(int i = 1; i <= 22; ++i)
{
binary.push(x % 2);
x = x/2;
}
Node* temp = trie;
while(binary.empty() == false)
{
if(temp->v[!binary.top()] == nullptr)
temp = temp->v[binary.top()];
else
temp = temp->v[!binary.top()];
binary.pop();
}
return copy_x ^ temp->number;
}
int v[100001], N;
ifstream fin{"xormax.in"};
ofstream fout("xormax.out");
int main()
{
fin >> N;
for(int i = 1; i <= N; ++i)
{
fin >> v[i];
v[i] ^= v[i - 1];
push_trie(v[i]);
}
int MAX = -1000000000;
int stop = 0;
int start = 0;
for(int i = 1; i <= N; ++i)
{
int current = max_trie(v[i]);
if(current >= MAX)
{
MAX = current;
stop = i;
}
}
int xorsum = 0;
for(int i = stop; i > 0; --i)
{
xorsum ^= (v[i] ^ v[i - 1]);
if(xorsum == MAX)
{
start = i;
break;
}
}
fout << MAX << " " << start << " " << stop;
}