Submission #87410

#	Time	Username	Problem	Language	Result	Execution time	Memory
87410		wzy	XOR (IZhO12_xor)	C++11	100 / 100	506 ms	100608 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ll long long
struct node{
	int bt , ist , idrmq = 1000000;
	node *f[2];
};

node * trie;

void insert(int cbit, int vl , int idx,  node*& root){
	if(cbit < 0){
		root->idrmq = min(idx , root->idrmq);
		root->ist = 1;
		root->bt = cbit;
		return ;
	}
	bool t = (((1<<cbit) & vl) ? 1 : 0);
	if(root->f[t]){
		insert(cbit-1 , vl , idx , root->f[t]);
	}
	else{
		root->f[t] = new node();
		root->f[t]->bt = cbit - 1;
		root->f[t]->idrmq = idx;
		insert(cbit-1 , vl , idx , root->f[t]);
	}
	if(root->f[0]) root->idrmq = min(root->idrmq , root->f[0]->idrmq);
	if(root->f[1]) root->idrmq = min(root->idrmq, root->f[1]->idrmq);
}

int query(int vl , int cbit, bool mt , int X ,  node * root){
	if(cbit < 0){
		return root->idrmq;
	}
	if(mt){
		if(1<<cbit & X){
			bool P = (1<<cbit & vl ? 1 : 0);
			P = !P;
			if(root->f[P]){
				return query(vl , cbit - 1 , 1 , X , root->f[P]);
			}
			else return 10000000;
		}
		else{
			bool P = (1<<cbit & vl ? 1 : 0);
			int Pl = 10000000;
			if(root->f[P]) Pl  =query(vl , cbit-1 , 1 , X , root->f[P]);
			if(root->f[!P]) Pl = min(Pl , query(vl, cbit-1, 0,X , root->f[!P]));
			return Pl;
		}

	}
	else{
		return root->idrmq;
	}
}
int n , x;
int V[250005];

struct ans{
	int id , k;
	bool operator<(const ans X){
		if(X.k == k){
			return id > X.id;
		}
		return k < X.k;
	}
} ;

int32_t main(){
	scanf("%d%d" , &n , &x);
	trie = new node();
	ans curr;
	curr.k = -1;
	for(int i = 1 ; i <= n; i ++){
		scanf("%d" , &V[i]);
		V[i] ^= V[i-1];
		insert(30 , V[i] , i ,trie);
		int U = query(V[i] , 30 , 1 , x ,trie );
		U++;
		ans P = {U , i - U  + 1};
		if(curr < P) curr = P;
	}
	printf("%d %d\n" , curr.id , curr.k);
}

Compilation message (stderr)

xor.cpp: In function 'int32_t main()':
xor.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &x);
  ~~~~~^~~~~~~~~~~~~~~~~~
xor.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &V[i]);
   ~~~~~^~~~~~~~~~~~~~
xor.cpp:69:18: warning: 'curr.ans::id' may be used uninitialized in this function [-Wmaybe-uninitialized]
    return id > X.id;
                  ^~
xor.cpp:78:6: note: 'curr.ans::id' was declared here
  ans curr;
      ^~~~

• Subtask 1: 100 / 100