Submission #1263569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263569		aren_dance	Cave (IOI13_cave)	C++20	100 / 100	361 ms	604 KiB

cave

#include <iostream>
#include <vector>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int s[N] = { -1 };
int d[N] = { -1 };
/*o[0] = 0;
o[1] = 0;
o[2] = 0;
o[3] = 0;
per[0] = 2;
per[1] = 1;
per[2] = 3;
per[3] = 0;*/
for (int i = 0;i < N;++i) {
	int p[N] = { 0 };
	vector<int> k;
	vector<bool> mas(N,0);
	for (int j = 0;j < i;++j) {
		p[d[j]] = s[d[j]];
		mas[d[j]] = 1;
	}
	for (int j = 0;j < N;++j) {
		if (!mas[j]) {
			k.push_back(j);
			p[j] = 0;
		}
	}
	int v = tryCombination(p);
	int x = 1;
	if (v == -1 || v > i) {
		x = 0;
	}
	int r = k.size()-1;
	int l = 0;
	int answ = k[r];
	while (l <= r)	{
		int p[N];
		for (int j = 0;j < N;++j) {
			p[j] = x^1;
		}
		int m = (l + r) / 2;
		for (int j = 0;j <= m;++j) {
			p[k[j]] = x;
		}
		for (int j = 0;j < i;++j) {
			p[d[j]] = s[d[j]];
		}
		int u = tryCombination(p);
		if (u > i || u==-1) {
			r = m - 1;
			answ = k[m];
		}
		else {
			l = m + 1;
		}
	}
	d[i] = answ;
	s[answ] = x;
}
int e[N];
for (int i = 0;i < N;++i) {
	e[d[i]] = i;
}
answer(s,e);
}

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