Submission #4812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4812	2014-01-04T12:18:16 Z	tncks0121	XOR (IZhO12_xor)	C++	0 / 100	48 ms	2184 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 = 3;

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

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2184 KB	Output isn't correct
2	Incorrect	0 ms	2184 KB	Output isn't correct
3	Incorrect	0 ms	2184 KB	Output isn't correct
4	Incorrect	0 ms	2184 KB	Output isn't correct
5	Incorrect	0 ms	2184 KB	Output isn't correct
6	Incorrect	4 ms	2184 KB	Output isn't correct
7	Incorrect	4 ms	2184 KB	Output isn't correct
8	Incorrect	4 ms	2184 KB	Output isn't correct
9	Incorrect	20 ms	2184 KB	Output isn't correct
10	Incorrect	16 ms	2184 KB	Output isn't correct
11	Incorrect	20 ms	2184 KB	Output isn't correct
12	Incorrect	16 ms	2184 KB	Output isn't correct
13	Incorrect	16 ms	2184 KB	Output isn't correct
14	Incorrect	16 ms	2184 KB	Output isn't correct
15	Incorrect	20 ms	2184 KB	Output isn't correct
16	Incorrect	8 ms	2184 KB	Output isn't correct
17	Incorrect	48 ms	2184 KB	Output isn't correct
18	Incorrect	44 ms	2184 KB	Output isn't correct
19	Incorrect	44 ms	2184 KB	Output isn't correct
20	Incorrect	44 ms	2184 KB	Output isn't correct