답안 #468917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468917	2021-08-30T07:44:17 Z	Radman_	XOR (IZhO12_xor)	C++14	100 / 100	505 ms	85828 KB

xor

//                  //
//     Radmanシ     //
//                 //
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<stack>

using namespace std;

//#define int long long

typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
#define F first
#define S second

const int maxn=2.5e5+5,inf=2e9;
int a[maxn],ps[maxn];
string s[maxn];

struct Node
{
    Node *child[2];
    int height,mini;
    Node()
    {
        mini=inf;
        for(int i=0;i<2;i++)
            child[i]=nullptr;
    }
};

struct Trie
{
    Node *root;
    int strType,cnt;
    Trie()
    {
        strType='0';
        root=new Node();
    }
    void add(string st,int num)
    {
        Node *cur=root;
        cur->mini=min(cur->mini,num);
        for(char c:st)
        {
            int x=int(c)-strType;
            if(cur->child[x]==nullptr)
                cur->child[x]=new Node();
            cur=cur->child[x];
            cur->mini=min(cur->mini,num);
        }
        return;
    }
};

string mabnaye2(int n)
{
    string ans="";
    while(n>0)
    {
        ans+=(char)((n%2)+'0');
        n/=2;
    }
    while(ans.size()<30)
    	ans=ans+'0';
    reverse(ans.begin(),ans.end());
    return ans;
}

int n,X,maxi=0,ind=0;
string sx="";
void find(int ii,Node *root)
{
    Node *cur=root;
    for(int i=0;i<30;i++)
    {
    	int x=sx[i]-'0';
    	int y=s[ii][i]-'0';
    	int z,c;
    	if(y==0)
    	{
    		if(cur->child[1])
    		{
    			c=1;
    			z=1;
    		}
    		else
    		{
    			c=0;
    			z=0;
    		}
    	}
    	else
    	{
    		if(cur->child[0])
    		{
    			c=0;
    			z=1;
    		}
    		else
    		{
    			c=1;
    			z=0;
    		}
    	}
    	if(z<x)
    		return;
    	if(z>x)
    	{
    		cur=cur->child[c];
    		int tmp=cur->mini;
    		if(maxi<ii-tmp)
    		{
    			ind=tmp+1;
    			maxi=ii-tmp;
    		}
    		return;
    	}
    	cur=cur->child[c];
    }
    int tmp=cur->mini;
 	if(maxi<ii-tmp)
   	{
    	ind=tmp+1;
    	maxi=ii-tmp;
	}
    return;
}

int32_t main()
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Trie* T=new Trie();
    cin>>n>>X;
    sx=mabnaye2(X);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ps[i]=(ps[i-1]^a[i]);
    }
    s[0]=mabnaye2(0);
    T->add(s[0],0);
    for(int i=1;i<=n;i++)
    {
    	s[i]=mabnaye2(ps[i]);
    	if(a[i]>X and maxi<1)
    	{
    		maxi=1;
    		ind=i;
    	}
    	find(i,T->root);
    	T->add(s[i],i);
    }
    cout<<ind<<' '<<maxi<<endl;
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	8140 KB	Output is correct
2	Correct	5 ms	8140 KB	Output is correct
3	Correct	5 ms	8140 KB	Output is correct
4	Correct	9 ms	8524 KB	Output is correct
5	Correct	65 ms	11440 KB	Output is correct
6	Correct	58 ms	12188 KB	Output is correct
7	Correct	63 ms	12228 KB	Output is correct
8	Correct	67 ms	12616 KB	Output is correct
9	Correct	191 ms	43204 KB	Output is correct
10	Correct	200 ms	43308 KB	Output is correct
11	Correct	190 ms	43188 KB	Output is correct
12	Correct	185 ms	43188 KB	Output is correct
13	Correct	184 ms	43236 KB	Output is correct
14	Correct	182 ms	43260 KB	Output is correct
15	Correct	186 ms	43260 KB	Output is correct
16	Correct	185 ms	43168 KB	Output is correct
17	Correct	478 ms	85784 KB	Output is correct
18	Correct	473 ms	85828 KB	Output is correct
19	Correct	505 ms	85820 KB	Output is correct
20	Correct	466 ms	85828 KB	Output is correct