Submission #447574

#	Time	Username	Problem	Language	Result	Execution time	Memory
447574		asbsfds	XOR (IZhO12_xor)	C++14	0 / 100	141 ms	28048 KiB

xor

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

struct node {
	node *l, *r;
	int mini;
	
	node() {
		mini = inf;
		l = r = nullptr;
	}
};

int n, x;
int niz[maxn];
node* root;

int get_value(node *tren) {
	if (tren == nullptr) return inf;
	return tren->mini;
}

void insert(int x, int val, int iter = 31, node* tren = root) {
	if (iter < 0) {
		tren->mini = min(tren->mini, val);
		return;
	}
	
	node* nex;
	if (x & (1 << iter)) {
		if (tren->r == nullptr) tren->r = new node;
		nex = tren->r;
	} else {
		if (tren->l == nullptr) tren->l = new node;
		nex = tren->l;
	}
	insert(x, val, iter - 1, nex);
	tren->mini = min(get_value(tren->l), get_value(tren->r));
}

int query(int x, int iter = 31, node* tren = root) {
	if (tren == nullptr) return inf;
	if (iter < 0) return tren->mini;
	
	int out = inf;
	if ((::x & (1 << iter)) == 0) {
		if (x & (1 << iter)) out = min(query(x, iter - 1, tren->r), get_value(tren->l));
		else out = min(query(x, iter - 1, tren->l), get_value(tren->r));
	} else {
		if (x & (1 << iter)) out = query(x, iter - 1, tren->l);
		else out = query(x, iter - 1, tren->r);
	}
	return out;
}

int main() {
	scanf("%d%d", &n, &x);
	for (int i = 1; i <= n; i++)
		scanf("%d", niz+i);
	
	root = new node;
	insert(0, 0);
	for (int i = 1; i <= n; i++) {
		niz[i] ^= niz[i - 1];
		insert(niz[i], i);
	}
	
	int a = -1, k = -1;
	for (int i = 1; i <= n; i++) {
		int x = query(niz[i]);
		//printf("debug: %d %d\n", x + 1, i);
		if (k < i - x) {
			a = x + 1;
			k = i - x;
		}
	}
	if (k <= 0) printf("-1\n");
	else printf("%d %d\n", a, k);
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d", &n, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100