Submission #342810

#	Time	Username	Problem	Language	Result	Execution time	Memory
342810		wwdd	Cave (IOI13_cave)	C++14	100 / 100	232 ms	1012 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int LOG = 13;

void exploreCave(int N) {
	int ges[LOG][N];
	int los[N];
	int fig[N];
	int rep[N],ros[N];
	memset(fig,0,sizeof(fig));
	memset(los,0,sizeof(los));
	for(int i=0;i<LOG;i++) {
		for(int j=0;j<N;j++) {
			ges[i][j] = ((j&(1<<i))?1:0);
		}
	}
	for(int i=0;i<N;i++) {
		int idx = 0;
		ii reb = {-1,-1};
		for(int j=0;j<LOG;j++) {
			int num = tryCombination(ges[j]);
			if(num > i || num == -1) {
				idx |= (1<<j);
			}
		}
		int comp = ((1<<LOG)-1-idx);
		if(comp >= N || fig[comp]) {
			reb = {idx,1};
		} else if(idx >= N || fig[idx]) {
			reb = {comp,0};
		} else {
			los[idx] = los[comp] = 1;
			int num = tryCombination(los);
			if(num > i || num == -1) {
				reb = {idx,1};
			} else {
				reb = {comp,0};
			}
		}
		los[reb.first] = reb.second;
		rep[reb.first] = i;
		ros[reb.first] = reb.second;
		fig[reb.first] = 1;
		for(int j=0;j<LOG;j++) {
			ges[j][reb.first] = reb.second;
		}
	}
	answer(ros,rep);
}

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