Submission #798515

#	Time	Username	Problem	Language	Result	Execution time	Memory
798515		QwertyPi	Cave (IOI13_cave)	C++14	0 / 100	286 ms	448 KiB

cave

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

using namespace std;

int N;
const int N_MAX = 5000;
bool U[N_MAX] = {};
int S[N_MAX], D[N_MAX], T[N_MAX];

int selfTryCombination(int T[]){
	int r = tryCombination(T);
	return r == -1 ? N : r;
}

int BS(int i, int s, vector<int>& v, int l, int r){
	if(l + 1 == r) return v[l];
	int mid = (l + r) / 2;
	for(int j = 0; j < N; j++) T[j] = S[j];
	for(int j = 0; j < v.size(); j++) T[v[j]] = !s;
	for(int j = l; j < mid; j++) T[v[j]] = s;
	int rr = selfTryCombination(T);
	int ok = rr >= i + 1;
	if(ok){
		return BS(i, s, v, l, mid);
	}else{
		return BS(i, s, v, mid, r);
	}
}

void exploreCave(int N) {
	::N = N;
	for(int i = 0; i < N; i++){
		vector<int> v; for(int j = 0; j < N; j++) if(!U[j]) v.push_back(j);
		for(int j = 0; j < N; j++) T[j] = S[j];
		for(auto i : v) T[i] = 1;
		int r = selfTryCombination(T);
		int s = r >= i + 1;
		int nxt = BS(i, s, v, 0, v.size());
		S[nxt] = s; D[nxt] = i; U[nxt] = false;
	}
	answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'int BS(int, int, std::vector<int>&, int, int)':
cave.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int j = 0; j < v.size(); j++) T[v[j]] = !s;
      |                 ~~^~~~~~~~~~

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