Submission #171055

#	Time	Username	Problem	Language	Result	Execution time	Memory
171055		dennisstar	Cave (IOI13_cave)	C++11	100 / 100	1060 ms	648 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

vector<pii> ar;
int S[5010];
int ans1[5010], ans2[5010];
inline void fchk() {for (pii pi:ar) S[pi.fi]=pi.se;}

void exploreCave(int N) {
	int s, e, md, type;
	int tC;
	for (int i=0; i<N; i++) {
		fill(S, S+N, 0);
		fchk();
		tC=tryCombination(S);
		if (tC>i||tC==-1) type=0;
		else type=1;
		s=0, e=N;
		while (s+1<e) {
			md=(s+e)/2;
			fill(S, S+N, 1-type);
			fill(S+s, S+md, type);
			fchk();
			tC=tryCombination(S);
			if (tC>i||tC==-1) e=md;
			else s=md;
		}
		ar.push_back({s, type});
	}
	for (int i=0; i<N; i++) {
		ans1[ar[i].fi]=ar[i].se;
		ans2[ar[i].fi]=i;
	}
	answer(ans1, ans2);
}

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