Submission #208562

#	Time	Username	Problem	Language	Result	Execution time	Memory
208562		teomrn	Cave (IOI13_cave)	C++14	100 / 100	617 ms	640 KiB

cave

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

void exploreCave(int N)
{
	vector <int> switches(N);
	iota(switches.begin(), switches.end(), 0);
	vector <int> ans(N), coresp(N);
	vector <int> question(N);

	for (int door = 0; door < N; door++) {
		// vreau sa deschid usa door
		int value = 0;
		for (auto i : switches)
			question[i] = 0;
		int guess = tryCombination(question.data());
		
		if (guess <= door && guess != -1)
			value = 1; /// usa o sa se deschida cu switch-ul pe 1

		int p = -1;

		for (int q = (1 << 20); q; q /= 2) {
			if (p + q + 1 < switches.size()) {
				int val = p + q;
				for (int i = 0; i <= val; i++)
					question[switches[i]] = 1 - value;
				for (int i = val + 1; i < (int)switches.size(); i++)
					question[switches[i]] = value;
				int guess = tryCombination(question.data());

				if (guess > door || guess == -1)
					p += q;
			}
		}

		p = switches[p + 1];
		/// usa door este actionata de switch-ul p
	
		coresp[p] = door;
		ans[p] = value;
		question[p] = value;

		switches.erase(find(switches.begin(), switches.end(), p));
	}

	answer(ans.data(), coresp.data());
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (p + q + 1 < switches.size()) {
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~

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