Pagini recente » Cod sursa (job #1619911) | Cod sursa (job #3040480) | Cod sursa (job #2941513) | Cod sursa (job #2252836) | Cod sursa (job #3167030)
/*
"care a facut teste cu Lattice reduction attack e ciudat"
"linistiti va putin"
- 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
struct Node
{
int prefpos;
int muchii[2];
};
int v[100001];
int prefxor[100001];
Node trie[2200000];
int sz,currpos;
void ins(string s)
{
int node;
int j;
node=0;
for (j=0; j<s.size(); j++)
{
if (trie[node].muchii[s[j]-'0']==0)
{
sz++;
trie[sz]= {0,0};
trie[node].muchii[s[j]-'0']=sz;
}
node=trie[node].muchii[s[j]-'0'];
}
trie[node].prefpos=max(currpos,trie[node].prefpos);
}
int bestnode;
string best(string s)
{
int j;
int node;
int secondnode;
node=0;
secondnode=0;
string res;
for (j=0; j<s.size(); j++)
{
if (s[j]=='1')
{
node=trie[node].muchii[1];
if (trie[secondnode].muchii[0]==0)
{
secondnode=trie[secondnode].muchii[1];
res+="1";
}
else
{
secondnode=trie[secondnode].muchii[0];
res+="0";
}
}
else
{
node=trie[node].muchii[0];
if (trie[secondnode].muchii[1]==0)
{
secondnode=trie[secondnode].muchii[0];
res+="0";
}
else
{
secondnode=trie[secondnode].muchii[1];
res+="1";
}
}
}
bestnode=secondnode;
return res;
}
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,i,j,mx,ans,maxl,l,r;
string s,s2;
fin >> n;
for (j=1; j<=n; j++)
{
fin >> v[j];
prefxor[j]=prefxor[j-1]^v[j];
}
trie[0]= {0,0};
sz=0;
mx=0;
for (j=1; j<=n; j++)
{
currpos=j;
s="";
for (i=21; i>=0; i--)
{
if (prefxor[j]&(1<<i))
s+="1";
else
s+="0";
}
ins(s);
bestnode=0;
s2=best(s);
maxl=trie[bestnode].prefpos+1;
reverse(s.begin(),s.end());
reverse(s2.begin(),s2.end());
ans=0;
for (i=0; i<=21; i++)
{
if (s[i]!=s2[i])
ans+=(1<<i);
}
if (ans>=mx)
{
if (ans==mx)
{
if (j<r)
{
mx=ans;
r=j;
l=maxl;
}
else if (j==r && maxl>l)
{
mx=ans;
r=j;
l=maxl;
}
}
else
{
mx=ans;
r=j;
l=maxl;
}
}
}
fout << mx << " " << l << " " << r;
}