Pagini recente » Cod sursa (job #114393) | Cod sursa (job #2325776) | Cod sursa (job #2636023) | Cod sursa (job #3221204) | Cod sursa (job #2985181)
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#define ll long long
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n, s[100001], pos;
struct trie
{
vector<int> cnt;
trie* next[2];
trie()
{
next[0] = nullptr;
next[1] = nullptr;
}
void insert(int nr,int p)
{
if (p == 0)
cnt.push_back(pos);
else
{
int ok = 0;
if (nr & p)
ok = 1;
if (next[ok] == nullptr)
next[ok] = new trie;
next[ok]->insert(nr, p / 2);
}
}
};
trie* r = new trie;
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] ^= s[i - 1];
pos = i;
r->insert(s[i],(1<<20));
}
int s1 = 0, s2 = 0;
trie* c = r;
for(int i=20;i>=0;i--)
{
if (r->next[1] != nullptr && c->next[0] != nullptr)
{
s1 += (1 << i);
r = r->next[1];
c = c->next[0];
}
else if (r->next[0] != nullptr && c->next[1] != nullptr)
{
s2 += (1 << i);
r = r->next[0];
c = c->next[1];
}
else if (r->next[0] != nullptr && c->next[0] != nullptr)
{
//s1 += (1 << i);
r = r->next[0];
c = c->next[0];
}
else if (r->next[1] != nullptr && c->next[1] != nullptr)
{
s1 += (1 << i);
s2 += (1 << i);
r = r->next[1];
c = c->next[1];
}
}
sort(c->cnt.begin(), c->cnt.end());
sort(r->cnt.begin(), r->cnt.end());
cout << (s2 ^ s1) << ' ';
if (s1 < s2)
cout << c->cnt[0] + 1 << ' ' << r->cnt[0];
else
cout << r->cnt[0] + 1 << ' ' << c->cnt[0];
return 0;
}