oj.uz

답안 #320699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320699 2020-11-09T14:31:24 Z egod1537 동굴 (IOI13_cave) C++14
13 / 100
 385 ms 612 KB 
#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(state > i) {
				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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 488 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 484 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 259 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 298 ms 492 KB Output is correct
7 Correct 231 ms 612 KB Output is correct
8 Correct 372 ms 500 KB Output is correct
9 Correct 385 ms 492 KB Output is correct
10 Correct 373 ms 612 KB Output is correct
11 Correct 236 ms 492 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Answer is wrong
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Answer is wrong
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 488 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -