제출 #650071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650071		groshi	XOR (IZhO12_xor)	C++17	100 / 100	137 ms	90288 KiB

xor

#include<iostream>

using namespace std;
struct wi{
    int t[2];
    int minn=1e9;
}*w;
int nowy=2;
int szukaj(int jest,int co,int x,int gdzie)
{
    if(gdzie==-1)
        return w[jest].minn;
    int mam=x&(1<<gdzie);
    if(mam==0)
    {
        int cos;
        mam=co&(1<<gdzie);
        if(mam==0)
            cos=0;
        else cos=1;
        if(w[jest].t[!cos]!=0)
            return w[w[jest].t[!cos]].minn;
        else if(w[jest].t[cos]==0)
            return 1e9;
        else return szukaj(w[jest].t[cos],co,x,gdzie-1);
    }
    else{
        int cos;
        mam=co&(1<<gdzie);
        if(mam==0)
            cos=0;
        else cos=1;
        if(w[jest].t[!cos]==0)
            return 1e9;
        else return szukaj(w[jest].t[!cos],co,x,gdzie-1);
    }
}
void dodaj(int x,int co,int gdzie,int nr)
{
    w[x].minn=min(w[x].minn,nr);
    if(gdzie==-1)
        return;
    int cos;
    int mam=co&(1<<gdzie);
    if(mam==0)
        cos=0;
    else cos=1;
    if(w[x].t[cos]==0)
    {
        w[x].t[cos]=nowy;
        nowy++;
        dodaj(nowy-1,co,gdzie-1,nr);
    }
    else dodaj(w[x].t[cos],co,gdzie-1,nr);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,x,y;
    cin>>n>>x;
    w=new wi[n*30];
    int xorr=0;
    int wynik=0;
    int pocz=0;
    for(int i=1;i<=n;i++)
    {
        cin>>y;
        xorr^=y;
        if(xorr>=x)
        {
            wynik=i;
            pocz=1;
        }
        int gdzie=szukaj(1,xorr,x,30);
        if(i-gdzie>wynik)
        {
            wynik=i-gdzie;
            pocz=gdzie+1;
        }
        dodaj(1,xorr,30,i);
    }
    cout<<pocz<<" "<<wynik;
    return 0;
}

• Subtask 1: 100 / 100