Submission #468917

#	Time	Username	Problem	Language	Result	Execution time	Memory
468917		Radman_	XOR (IZhO12_xor)	C++14	100 / 100	505 ms	85828 KiB

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 / 100