제출 #4817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4817		tncks0121	XOR (IZhO12_xor)	C++98	100 / 100	252 ms	58284 KiB

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 = 0; 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(now != NULL) r = max(r, now->x);
		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: 100 / 100