제출 #314661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
314661		jaaguptamme	동굴 (IOI13_cave)	C++17	100 / 100	1025 ms	760 KiB

cave

#include <bits/stdc++.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