Submission #320700

#	Time	Username	Problem	Language	Result	Execution time	Memory
320700		egod1537	Cave (IOI13_cave)	C++14	13 / 100	383 ms	484 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);
			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: 0 / 12
• Subtask 2: 13 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24