제출 #320709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320709		egod1537	동굴 (IOI13_cave)	C++14	100 / 100	436 ms	640 KiB

cave

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

using namespace std;

int n;
int* arr, * con;
bitset<5001> vit;

//int tryCombination(int S[]) {
//	for (int i = 0; i < n; i++)
//		cout << S[i] << " ";
//	cout << "\n";
//
//	int ret; cin >> ret;
//	return ret;
//}

void rev(int s, int e) {
	for (int i = s; i <= e; i++) {
		if (vit[i]) continue;
		arr[i] = !arr[i];
	}
}

void exploreCave(int _n) {
	n = _n;
	arr = new int[n];
	con = new int[n];
	fill(arr, arr + n, 0);
	fill(con, con + n, 0);

	for (int i = 0; i < n; i++) {
		int lo = 0, hi = n - 1;
		int state = tryCombination(arr);
		if (state == -1) state = n;

		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			rev(lo, mid);
			int now = tryCombination(arr);
			if (now == -1) now = n;
			rev(lo, mid);

			//case1 i번째 문이 닫혀 있는 경우
			if (state == i) {
				if (now > i) hi = mid - 1;
				else lo = mid + 1;
			}
			//case2 i번째 문이 열려있는 경우
			else {
				if (now == i) hi = mid - 1;
				else lo = mid + 1;
			}
		}

		if (lo == n) lo = 0;
		if (state == i) arr[lo] = !arr[lo];

		//cout << "result : " << i << " " << lo << "\n";
		con[lo] = i;
		vit[lo] = true;
	}

	//for (int i = 0; i < n; i++)
	//	cout << arr[i] << " ";
	//cout << "\n";
	//for (int i = 0; i < n; i++)
	//	cout << con[i] << " ";
	//cout << "\n";

	answer(arr, con);
}

//int main() {
//	exploreCave(4);
//	return 0;
//}

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