Submission #115352

#	Time	Username	Problem	Language	Result	Execution time	Memory
115352		suzy	Cave (IOI13_cave)	C++17	100 / 100	1326 ms	520 KiB

cave

#include <string.h>
#include "cave.h"

int n, s[5001], d[5001], a[5001], b[5001];

void exploreCave(int N) {
	memset(d, -1, sizeof(d));
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[j] >= 0) s[j] = d[j];
			else s[j] = 0;
		}
		int w = tryCombination(s);
		int lo = 0, hi = n;
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			for (int j = 0; j < n; j++) {
				if (d[j] >= 0) s[j] = d[j];
				else {
					if (j < mid) s[j] = 1;
					else s[j] = 0;
				}
			}
			int y = tryCombination(s);
			if (w == i) {
				if (w != y) hi = mid;
				else lo = mid;
			}
			else {
				if (y == i) hi = mid;
				else lo = mid;
			}
		}
		a[lo] = i;
		d[lo] = (w == i ? 1 : 0);
	}
	answer(d, a);
}

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