제출 #1132385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132385		sofija6	XOR (IZhO12_xor)	C++17	100 / 100	108 ms	42480 KiB

xor

#include <bits/stdc++.h>
#define ll long long
#define MAXN 250010
#define MAXV 7000010
#define llinf 1e17
using namespace std;
ll x,nextt[MAXV][2],vall[MAXV],cnt=2,ans;
void Add(ll ind,ll val,ll pos,ll i)
{
    if (pos<0)
        return;
    ll cur=(val&(1<<pos))!=0;
    if (!nextt[ind][cur])
    {
        nextt[ind][cur]=cnt++;
        vall[nextt[ind][cur]]=llinf;
    }
    vall[nextt[ind][cur]]=min(vall[nextt[ind][cur]],i);
    Add(nextt[ind][cur],val,pos-1,i);
}
void Find(ll ind,ll val,ll pos)
{
    ll cura=(val&(1<<pos))!=0,curx=(x&(1<<pos))!=0;
    if (pos<0)
    {
        ans=min(ans,vall[ind]);
        return;
    }
    if (curx)
    {
        ll curr=curx^cura;
        if (!nextt[ind][curr])
            return;
        Find(nextt[ind][curr],val,pos-1);
        return;
    }
    ll curr=1^cura;
    if (nextt[ind][curr])
        ans=min(ans,vall[nextt[ind][curr]]);
    if (nextt[ind][curr^1])
        Find(nextt[ind][curr^1],val,pos-1);
    return;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,a,ansi,ansk=0,pref=0;
    cin >> n >> x;
    Add(1,0,29,0);
    for (ll i=1;i<=n;i++)
    {
        cin >> a;
        pref^=a;
        ans=llinf;
        Find(1,pref,29);
        if (ans!=llinf && i-ans>ansk)
        {
            ansk=i-ans;
            ansi=ans+1;
        }
        Add(1,pref,29,i);
    }
    cout << ansi << " " << ansk << "\n";
    return 0;
}

• Subtask 1: 100 / 100