Pagini recente » Cod sursa (job #8259) | Cod sursa (job #1763407) | Cod sursa (job #1409295) | Cod sursa (job #2561854) | Cod sursa (job #3187574)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int N = 100005;
int nr;
struct trie{
trie *leg[2];
int val;
trie(){
leg[0] = nullptr;
leg[1] = nullptr;
val = 0;
}
};
struct solution{
int val;
int step;
} dp[N];
trie *root = new trie;
void add(trie *node, int pos, int step){
if(pos == -1){
node->val = step;
return;
}
int ch = nr&(1<<pos);
if(ch>0)
ch = 1;
if(!node->leg[ch])
node->leg[ch] = new trie;
node->val = step;
add(node->leg[ch],pos-1,step);
}
solution xormax(trie *node, int pos){
solution sol;
if(pos == -1){
sol.val = 0;
sol.step = node->val;
return sol;
}
int ch = nr&(1<<pos);
if(ch>0)
ch = 1;
if(node->leg[1-ch]){
sol.val = (1<<pos)+xormax(node->leg[1-ch],pos-1).val;
sol.step = xormax(node->leg[1-ch],pos-1).step;
return sol;
}
else{
sol.val = xormax(node->leg[ch],pos-1).val;
sol.step = xormax(node->leg[ch],pos-1).step;
return sol;
}
}
int main()
{
int n,i,xr,nmax = 0,ind = 0;
fin >> n;
xr = 0;
dp[0].val = 0; dp[0].step = 0;
nr = 0; add(root,20,0);
for(i=1;i<=n;i++){
fin >> nr;
nr^=xr;
xr = nr;
dp[i] = xormax(root,20);
add(root,20,i);
}
for(i=1;i<=n;i++)
nmax = max(nmax,dp[i].val);
for(i=n;i>0;i--){
if(dp[i].val == nmax)
ind = i;
}
fout << nmax << " " << dp[ind].step+1 << " " << ind;
return 0;
}