답안 #17473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17473	2015-12-20T09:36:14 Z	gs14004	XOR (IZhO12_xor)	C++14	100 / 100	721 ms	195100 KB

xor

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, x;

struct node{
	node *ls, *rs;
	int minv;
	node(){
		ls = rs = NULL;
		minv = 1e9;
	}
}*root;

void add(node *p, int pos, int val, int dep){
	if(dep == -1){
		p->minv = min(p->minv, val);
		return;
	}
	if(!p->ls) p->ls = new node();
	if(!p->rs) p->rs = new node();
	if((pos >> dep) % 2 == 0){
		add(p->ls, pos, val, dep-1);
	}
	if((pos >> dep) % 2 == 1){
		add(p->rs, pos, val, dep-1);
	}
	p->minv = min(p->ls->minv, p->rs->minv);
}

int query(node *p, int pos, int dep){
	if(dep == -1) return p->minv;
	if(!p->ls) p->ls = new node();
	if(!p->rs) p->rs = new node();
	bool b1 = (pos >> dep) & 1, b2 = (x >> dep) & 1;
	if(!b1 && !b2) return min(p->rs->minv, query(p->ls, pos, dep-1));
	if(b1 && !b2) return min(p->ls->minv, query(p->rs, pos, dep-1));
	if(!b1 && b2) return query(p->rs, pos, dep-1);
	if(b1 && b2) return query(p->ls, pos, dep-1);
}

int main(){
	root = new node();
	cin >> n >> x;
	add(root, 0, 0, 29);
	int pxor = 0;
	int ret = 0, retp = 0;
	for(int i=1; i<=n; i++){
		add(root, pxor, i-1, 29);
		int t;
		scanf("%d",&t);
		pxor ^= t;
		int tmp = i - query(root, pxor, 29);
		if(ret < tmp){
			ret = tmp;
			retp = i;
		}
	}
	cout << retp - ret + 1 << " " << ret;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1852 KB	Output is correct
2	Correct	1 ms	1852 KB	Output is correct
3	Correct	0 ms	1852 KB	Output is correct
4	Correct	0 ms	2512 KB	Output is correct
5	Correct	28 ms	5152 KB	Output is correct
6	Correct	34 ms	5416 KB	Output is correct
7	Correct	37 ms	5416 KB	Output is correct
8	Correct	38 ms	5416 KB	Output is correct
9	Correct	276 ms	94912 KB	Output is correct
10	Correct	267 ms	95440 KB	Output is correct
11	Correct	270 ms	94780 KB	Output is correct
12	Correct	296 ms	95044 KB	Output is correct
13	Correct	257 ms	95176 KB	Output is correct
14	Correct	279 ms	95440 KB	Output is correct
15	Correct	260 ms	95176 KB	Output is correct
16	Correct	271 ms	95044 KB	Output is correct
17	Correct	721 ms	194836 KB	Output is correct
18	Correct	693 ms	195100 KB	Output is correct
19	Correct	703 ms	195100 KB	Output is correct
20	Correct	659 ms	194968 KB	Output is correct