답안 #87410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87410	2018-11-30T18:03:16 Z	wzy	XOR (IZhO12_xor)	C++11	100 / 100	506 ms	100608 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	628 KB	Output is correct
3	Correct	2 ms	628 KB	Output is correct
4	Correct	3 ms	884 KB	Output is correct
5	Correct	17 ms	2936 KB	Output is correct
6	Correct	24 ms	3336 KB	Output is correct
7	Correct	22 ms	3644 KB	Output is correct
8	Correct	25 ms	3892 KB	Output is correct
9	Correct	174 ms	42344 KB	Output is correct
10	Correct	172 ms	43236 KB	Output is correct
11	Correct	169 ms	43792 KB	Output is correct
12	Correct	176 ms	44604 KB	Output is correct
13	Correct	168 ms	45496 KB	Output is correct
14	Correct	169 ms	46404 KB	Output is correct
15	Correct	165 ms	47048 KB	Output is correct
16	Correct	168 ms	47748 KB	Output is correct
17	Correct	467 ms	94728 KB	Output is correct
18	Correct	465 ms	96868 KB	Output is correct
19	Correct	442 ms	98716 KB	Output is correct
20	Correct	506 ms	100608 KB	Output is correct