Submission #1147512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147512		KickingKun	Cave (IOI13_cave)	C++20	100 / 100	218 ms	592 KiB

cave

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

using namespace std;

void exploreCave(int N) {
    int s[N], d[N], tries[N];
    memset(d, -1, sizeof d);
	
    for (int room = 0; room < N; room++) {
		vector <int> consi;
		for (int i = 0; i < N; i++)
			if (d[i] == -1) consi.emplace_back(i);
		
		for (int i = 0; i < N; i++) {
			if (d[i] != -1) tries[i] = s[i];
			else tries[i] = 0;
		}
		
		int ask = tryCombination(tries); int state = -1;
		if (ask == -1 || ask > room) state = 0;
		else state = 1; 
		
		int low = 0, high = consi.size() - 1, pos = -1;
		while (low <= high) {
			int mid = (low + high) >> 1;
			for (int i = 0; i <= mid; i++) tries[consi[i]] = state;
			for (int i = mid + 1; i < consi.size(); i++) tries[consi[i]] = state ^ 1;
			int ask = tryCombination(tries);
			if (ask == -1 || ask > room) high = (pos = mid) - 1;
			else low = mid + 1;
		}
		
		int mySwitch = consi[pos];
		d[mySwitch] = room; 
		s[mySwitch] = state;
	}
	
	answer(s, d);
}

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