제출 #232880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232880		T0p_	동굴 (IOI13_cave)	C++14	100 / 100	871 ms	648 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int,int>
#define x first
#define y second
 
void exploreCave(int N) {
 
	int s[N], d[N];
	pii door[N];
 
	for(int i=0 ; i<N ; i++)
	{
		for(int j=0 ; j<N ; j++) s[j] = 0;
		for(int j=0 ; j<i ; j++) s[door[j].x] = door[j].y;
		int start = tryCombination(s);
		int bit;
		(start != i) ? bit = 0 : bit = 1;
		int l = 0, r = N-1;
		while(l != r)
		{
			int mid = (l+r)>>1;
			for(int j=0 ; j<N ; j++) s[j] = (bit^1);
			for(int j=l ; j<=mid ; j++) s[j] = bit;
			for(int j=0 ; j<i ; j++) s[door[j].x] = door[j].y;
			int ret = tryCombination(s);
			(ret != i) ? r = mid : l = mid+1;
		}
		door[i] = make_pair(l, bit);
	}
	for(int i=0 ; i<N ; i++)
	{
		s[door[i].x] = door[i].y;
		d[door[i].x] = i;
	}
	answer(s, d);
}

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