Submission #87408

#	Time	Username	Problem	Language	Result	Execution time	Memory
87408		wzy	XOR (IZhO12_xor)	C++11	0 / 100	3 ms	376 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;
		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(vl == 4){
	}
	if(cbit < 0){
		return root->idrmq;
	}
	if(mt){
		if(1<<cbit & X){
			if(root->f[1]) return query(vl , cbit-1 , mt , X , root->f[1]);
			else return 1000000;
		}
		else{
			int Pl = 10000000;
			if(root->f[1]) Pl  =query(vl , cbit-1 , 0 , X , root->f[1]);
			else if(root->f[0]) Pl = min(Pl , query(vl, cbit-1, 1,X , root->f[0]));
			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 );
		//cout<<V[i] << " " << U<<" " << i << endl;
		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:72: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:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &V[i]);
   ~~~~~^~~~~~~~~~~~~~
xor.cpp:65:18: warning: 'curr.ans::id' may be used uninitialized in this function [-Wmaybe-uninitialized]
    return id > X.id;
                  ^~
xor.cpp:74:6: note: 'curr.ans::id' was declared here
  ans curr;
      ^~~~

• Subtask 1: 0 / 100