제출 #766537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766537		Sohsoh84	동굴 (IOI13_cave)	C++17	100 / 100	207 ms	468 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 5000 + 10;

int *S, n, *comb, pans, *D, *F;

inline int get() {
	return tryCombination(comb);
}

inline void flip(int l, int r) {
	for (int i = l; i <= r; i++)
		if (!F[i])
			comb[i] ^= 1;
}

void solve(int ind, int l, int r) {
	if (l == r) {
		D[l] = ind;
		if (pans == ind)
			comb[l] ^= 1;
		S[l] = comb[l];
		F[l] = 1;
		return;
	}

	int mid = (l + r) >> 1;
	flip(l, mid);
	int x = get();
	flip(l, mid);

	if ((pans == ind) == (x == ind)) solve(ind, mid + 1, r);
	else solve(ind, l, mid);
}

void exploreCave(int N_) {
	n = N_;
	D = new int[n];
	S = new int[n];
	F = new int[n];
	comb = new int[n];	
	for (int i = 0; i < n; i++)
		F[i] = D[i] = S[i] = comb[i] = 0;

	for (int i = 0; i < n; i++) {
		pans = get();
		solve(i, 0, n - 1);
	}

	answer(S, D);
}

// TODO: remove extra one

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