답안 #650071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650071	2022-10-12T09:09:22 Z	groshi	XOR (IZhO12_xor)	C++17	100 / 100	137 ms	90288 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	9 ms	8276 KB	Output is correct
6	Correct	11 ms	10708 KB	Output is correct
7	Correct	12 ms	11100 KB	Output is correct
8	Correct	13 ms	12392 KB	Output is correct
9	Correct	49 ms	36296 KB	Output is correct
10	Correct	46 ms	36308 KB	Output is correct
11	Correct	49 ms	36304 KB	Output is correct
12	Correct	49 ms	36288 KB	Output is correct
13	Correct	48 ms	36308 KB	Output is correct
14	Correct	46 ms	36300 KB	Output is correct
15	Correct	46 ms	36296 KB	Output is correct
16	Correct	48 ms	36292 KB	Output is correct
17	Correct	137 ms	90288 KB	Output is correct
18	Correct	133 ms	90280 KB	Output is correct
19	Correct	125 ms	90284 KB	Output is correct
20	Correct	137 ms	90212 KB	Output is correct