Submission #157288

#	Time	Username	Problem	Language	Result	Execution time	Memory
157288		ZikXewen	동굴 (IOI13_cave)	C++11	100 / 100	366 ms	608 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

void exploreCave(int N){
	int st[N] = {}, nw[N] = {}, ga[N] = {}, ct = 0;
	vector<int> lf(N);
	iota(lf.begin(), lf.end(), 0);
	for(int i = 0; i < N; i++) {
		int l = 0, r = lf.size() - 1;
		bool op = (tryCombination(st) == i);
		while(l < r) {
			int m = (l + r) >> 1;
			copy(st, st + N, nw);
			for(int j = l; j <= m; j++) nw[lf[j]] = !st[lf[j]];
			if((tryCombination(nw) == i) != op) r = m;
			else l = m + 1;
		}
		st[lf[l]] = op;
		ga[lf[l]] = i; 
		lf.erase(lf.begin() + l);
	}
	answer(st, ga);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:6:42: warning: unused variable 'ct' [-Wunused-variable]
  int st[N] = {}, nw[N] = {}, ga[N] = {}, ct = 0;
                                          ^~

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