Submission #321170

#	Time	Username	Problem	Language	Result	Execution time	Memory
321170		vukasinbabic06	XOR (IZhO12_xor)	C++14	100 / 100	242 ms	59492 KiB

xor

#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;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:44:9: warning: unused variable 'j' [-Wunused-variable]
   44 |  int i, j, k;
      |         ^
xor.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d%d", &N, &X);
      |  ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:48:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   int v; scanf("%d", &v);
      |          ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100