| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 339169 | 2020-12-24T18:24:18 Z | scales | XOR (IZhO12_xor) | C++17 | 1379 ms | 25948 KB |
#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
long long t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
unordered_map<long long,long long> pos;
cin>>n;
cin>>w;
vector<long long> a(n),b(n);
cin>>a[0];
l=n+1;
r=-1;
pos[a[0]]=0;
for(i=1;i<n;i++)
{
cin>>x;
a[i]=a[i-1]^x;
pos[a[i]]=i;
//cout<<"a[i]="<<a[i]<<endl;
}
maxi=0;
for(i=0;i<n;i++)
{
y=w^a[i];
r=pos[y];
//cout<<"i="<<i<<" y="<<y<<" r="<<r<<endl;
if(r-i>maxi || ((r-i)==maxi && i+1<viv))
{
maxi=r-i;
viv=i+1;
}
}
vector<long long> st(31);
st[0]=1;
for(i=1;i<=30;i++)
{
st[i]=st[i-1]*2;
}
dno=0;
//cout<<"maxi="<<maxi<<endl;
for(i=30;i>=0;i--)
{
z=w&st[i];
if(z==0)
{
if(dno==0)
{
for(j=0;j<n;j++)
{
b[j]=a[j]&st[i];
}
l=n+1;
r=-1;
for(j=0;j<n;j++)
{
if(b[j]>0)
{
l=min(l,i);
r=max(r,i);
}
}
if(r-l>maxi || ((r-l)==maxi && l+1<viv))
{
maxi=r-l;
viv=l+1;
}
}
else
{
if(i==0)
{
//cout<<"aaaaaaaaa"<<endl;
}
pos.clear();
h=w+st[i];
h=h/st[i];
//cout<<"h="<<h<<endl;
for(j=0;j<n;j++)
{
b[j]=a[j]/st[i];
//cout<<"b[j]="<<b[j]<<" ";
}
//cout<<endl;
for(j=0;j<n;j++)
{
pos[b[j]]=j;
}
for(j=0;j<n;j++)
{
y=h^b[j];
r=pos[y];
if(r-j>maxi || ((r-l)==maxi && l+1<viv))
{
maxi=r-j;
viv=j+1;
}
}
}
}
else
{
dno=1;
}
//cout<<"i="<<i<<" maxi="<<maxi<<endl;
}
cout<<viv+1<<" "<<maxi<<endl;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 2 ms | 492 KB | Output is correct |
| 5 | Correct | 8 ms | 2540 KB | Output is correct |
| 6 | Correct | 14 ms | 2680 KB | Output is correct |
| 7 | Correct | 10 ms | 2680 KB | Output is correct |
| 8 | Correct | 11 ms | 2808 KB | Output is correct |
| 9 | Correct | 270 ms | 10932 KB | Output is correct |
| 10 | Correct | 293 ms | 11188 KB | Output is correct |
| 11 | Correct | 216 ms | 11092 KB | Output is correct |
| 12 | Correct | 206 ms | 10952 KB | Output is correct |
| 13 | Correct | 154 ms | 10932 KB | Output is correct |
| 14 | Correct | 199 ms | 10988 KB | Output is correct |
| 15 | Correct | 382 ms | 11060 KB | Output is correct |
| 16 | Correct | 163 ms | 11060 KB | Output is correct |
| 17 | Correct | 1150 ms | 25820 KB | Output is correct |
| 18 | Correct | 1010 ms | 25948 KB | Output is correct |
| 19 | Correct | 1379 ms | 25900 KB | Output is correct |
| 20 | Correct | 723 ms | 25948 KB | Output is correct |