제출 #640193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640193		ymm	Cave (IOI13_cave)	C++17	100 / 100	189 ms	676 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 5050;
static int D[N];
static int S[N];
static int rem[N];

static int ask(int l, int r)
{
	Loop (i,l,r)
		S[rem[i]] = 1;
	int ans = tryCombination(S);
	Loop (i,l,r)
		S[rem[i]] = 0;
	if (ans == -1)
		ans = N;
	return ans;
}

void exploreCave(int N)
{
	Loop (i,0,N)
		rem[i] = i;
	Loop (i,0,N) {
		bool open = ask(0, 0) != i;
		int l = 0, r = N-1-i;
		while (l < r) {
			int m = (l + r + 1)/2;
			if ((ask(l, m) > i) ^ open)
				r = m-1;
			else
				l = m;
		}
		D[rem[l]] = i;
		S[rem[l]] = !open;
		swap(rem[l], rem[N-1-i]);
	}
	answer(S, D);
}

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