Submission #973229

#	Time	Username	Problem	Language	Result	Execution time	Memory
973229		pcc	동굴 (IOI13_cave)	C++17	0 / 100	254 ms	620 KiB

cave

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


const int mxn = 5050;

namespace {
	int state[mxn],perm[mxn],pstate[mxn];
	int buf[mxn];
	int N;
	bool done[mxn];
}

void solve(int id){
	memset(buf,0,sizeof(buf));
	for(int i = 0;i<id;i++){
		buf[perm[i]] = state[i];
	}
	if(tryCombination(buf)>id)state[id] = 0;
	else state[id] = 1;
	vector<int> v;
	for(int i = 0;i<N;i++){
		if(done[i])continue;
		v.push_back(i);
	}
	int l = 0,r = v.size()-1;
	while(l != r){
		int mid = (l+r)>>1;
		for(auto &i:v)buf[i] = state[id]^1;
		for(int i = l;i<=mid;i++)buf[v[i]] = state[id];
		if(tryCombination(buf)>id)r = mid;
		else l = mid+1;
	}
	perm[id] = l;
	done[l] = true;
	return;
}

void exploreCave(int NN) {
	N = NN;
	for(int i = 0;i<N;i++){
		solve(i);
	}
	for(int i = 0;i<N;i++){
		pstate[perm[i]] = state[i];
	}
	answer(pstate,perm);
	return;
}

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