Submission #914502

#	Time	Username	Problem	Language	Result	Execution time	Memory
914502		lamter	Cave (IOI13_cave)	C++17	0 / 100	199 ms	348 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

const int N = 5005;

int m, now, a[N], b[N], has[N];
int was[N];

int get(void) {
	int res = tryCombination(a);
	return res;
}

void Switch(int l, int r) {
	for (int x = l; x <= r; x += 1)
		a[x] ^= 1;
}

void Do(int x, int l, int r) {
	if (l == r) {
		a[has[l]] = (get() == x ? 1 : 0);
		b[has[l]] = x;
		return;
	}

	int m = (l + r) / 2;
	Switch(l, m);
	int nxt = get();
	Switch(l, m);

	if (now == x and nxt == x) {
		Do(x, m + 1, r);
	}

	if (now == x and nxt != x) {
		Do(x, l, m);
	}

	if (now != x and nxt == x) {
		Do(x, l, m);
	}

	if (now != x and nxt != x) {
		Do(x, m + 1, r);
	}
}

void exploreCave(int n) {
	for (int i = 0; i < n; i += 1) {
		m = 0;
		for (int j = 0; j < n; j += 1) if (not was[j]) {
			has[m++] = j;
		}
		now = get();
		Do(i, 0, m - 1);
	}
	answer(a, b);
}

#ifdef ILOVELAMTER
	int main(void) {
		return 0;
	}
#endif // ILOVELAMTER

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24