Submission #4813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4813	2014-01-04T12:20:10 Z	tncks0121	XOR (IZhO12_xor)	C++	10 / 100	240 ms	58284 KB

xor

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 250005;
int N, X, D[N_];

struct node {
	int x;
	node *child[2];
	node(): x(0) { child[0] = NULL; child[1] = NULL; }
};

node *root;

int res_i, res_k;
const int MAXB = 30;

int main() {
	int i, j, k;

	scanf("%d%d", &N, &X);
	for(i = 1; i <= N; i++) {
		int v; scanf("%d", &v);
		D[i] = D[i-1] ^ v;
	}

	root = new node;
	root->x = 0;
	
	for(i = 1; i <= N; i++) {
		node *now = root;
		for(k = MAXB; k >= 0; k--) {
			int d = (D[i] & (1<<k)) >> k;
			if(now->child[d] == NULL) now->child[d] = new node;
			now->child[d]->x = i;
			now = now->child[d];
		}
	}

	for(i = 0; i < N; i++) {
		node *now = root;
		int r = 0;
		for(k = MAXB; k >= 0; k--) {
			int d = (D[i] & (1<<k)) >> k;
			int x = (X    & (1<<k)) >> k;
			if(x == 0 && now->child[!d] != NULL) r = max(r, now->child[!d]->x);
			now = now->child[d^x];
			if(now == NULL) break;
		}
		if(res_k < r-i) res_i = i+1, res_k = r-i;
	}

	printf("%d %d\n", res_i, res_k);
	return 0;
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2184 KB	Output is correct
2	Incorrect	0 ms	2184 KB	Output isn't correct
3	Correct	0 ms	2184 KB	Output is correct
4	Incorrect	0 ms	2316 KB	Output isn't correct
5	Incorrect	12 ms	3504 KB	Output isn't correct
6	Incorrect	12 ms	3636 KB	Output isn't correct
7	Incorrect	12 ms	3636 KB	Output isn't correct
8	Incorrect	16 ms	3768 KB	Output isn't correct
9	Incorrect	88 ms	28584 KB	Output isn't correct
10	Incorrect	100 ms	28716 KB	Output isn't correct
11	Incorrect	88 ms	28452 KB	Output isn't correct
12	Incorrect	84 ms	28584 KB	Output isn't correct
13	Incorrect	92 ms	28584 KB	Output isn't correct
14	Incorrect	84 ms	28716 KB	Output isn't correct
15	Incorrect	92 ms	28584 KB	Output isn't correct
16	Incorrect	88 ms	28584 KB	Output isn't correct
17	Incorrect	220 ms	58152 KB	Output isn't correct
18	Incorrect	224 ms	58152 KB	Output isn't correct
19	Incorrect	240 ms	58284 KB	Output isn't correct
20	Incorrect	228 ms	58152 KB	Output isn't correct