Pagini recente » Cod sursa (job #724829) | Cod sursa (job #1728686) | Cod sursa (job #1002063) | Cod sursa (job #688720) | Cod sursa (job #3039836)
#include <fstream>
using namespace std;
const int NMAX = 100000;
int xorPartial[1 + NMAX]; /// xorPartial[i] = a1 xor a2 xor a3 xor ... xor ai
/// Ca la sume partiale.
///xorPartial[i - 1] ^ xorPartial[j] (pp. ca i <= j) = xorul elemenetelor ai, ai+1, ... , aj
class Trie
{
private:
static const int SIGMA = 2;
int frecventa;
Trie* fii[Trie::SIGMA];
Trie* tata;
int pozInTata;
public:
Trie() : frecventa(0), tata(nullptr), pozInTata(-1)
{
for (int i = 0; i < Trie::SIGMA; i++)
this->fii[i] = nullptr;
}
void adauga(const string& s, int indexXor, int index = 0)
{
if (index >= s.size())
{
this->frecventa = indexXor;
return;
}
if (this->fii[s[index] - '0'] == nullptr)
{
this->fii[s[index] - '0'] = new Trie();
this->fii[s[index] - '0']->tata = this;
this->fii[s[index] - '0']->pozInTata = s[index] - '0';
}
this->fii[s[index] - '0']->adauga(s, indexXor, index + 1);
}
int solutie(const string& s, int& solIndex, int index = 0, int adancime = 20)
{
if (index >= s.size())
{
solIndex = this->frecventa;
return 0;
}
if (s[index] == '1' && this->fii[0] != nullptr)
{
return (1 << adancime) + this->fii[0]->solutie(s, solIndex, index + 1, adancime - 1);
}
else if (s[index] == '1')
{
return this->fii[1]->solutie(s, solIndex, index + 1, adancime - 1);
}
else if (s[index] == '0' && this->fii[1] != nullptr)
{
return (1 << adancime) + this->fii[1]->solutie(s, solIndex, index + 1, adancime - 1);
}
else
{
return this->fii[0]->solutie(s, solIndex, index + 1, adancime - 1);
}
}
~Trie()
{
for (int i = 0; i < Trie::SIGMA; i++)
if (this->fii[i] != nullptr)
delete this->fii[i];
}
};
string toString(int x)
{
string sol = "";
if (x == 0)
sol.push_back('0');
while (x > 0)
{
sol.push_back((x % 2) + '0');
x /= 2;
}
while (sol.size() < 21)
sol.push_back('0');
for (int i = 0; i < sol.size() / 2; i++)
swap(sol[i], sol[sol.size() - 1 - i]);
return sol;
}
int main()
{
ifstream in("xormax.in");
ofstream out("xormax.out");
ios_base::sync_with_stdio(false);
in.tie(nullptr);
int n;
in >> n;
Trie* trie = new Trie();
int sol = 0;
int st = 1;
int dr = 1;
trie->adauga(toString(xorPartial[0]), 0);
for (int i = 1; i <= n; i++)
{
int x;
in >> x;
xorPartial[i] = xorPartial[i - 1] ^ x;
int solIndex;
int maxim = trie->solutie(toString(xorPartial[i]), solIndex);
trie->adauga(toString(xorPartial[i]), i);
if (sol < maxim)
{
sol = maxim;
st = solIndex + 1;
dr = i;
}
}
out << sol << ' ' << st << ' ' << dr << '\n';
delete trie;
return 0;
}