Submission #1267226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267226		cmiuc	Cave (IOI13_cave)	C++20	100 / 100	159 ms	552 KiB

cave

#include <iostream>
#include "cave.h"

using namespace std;
int Ans[5005], D[5005], S[5005], fxd[5005];

int ask(){
	int ans = tryCombination(S);
	if (ans == -1)
		ans = 5005;
	return ans;
}

void exploreCave(int n){

	for (int i=0;i<n;i++){
		int k = ask();

		int l = 0, r = n;
		while (l + 1 < r){
			int mid = (l + r) / 2;
			for (int j=l;j<mid;j++){
				if (!fxd[j])
					S[j] ^= 1;
			}
			int kk = ask();
			
			for (int j=l;j<mid;j++){
				if (!fxd[j])
					S[j] ^= 1;
			}
			
			if (k > i and kk > i)
				l = mid;
			else if (k > i)
				r = mid;
			else if (k == i and kk == i)
				l = mid;
			else
				r = mid;
		}
		D[l] = i;
		if (k == i)
			S[l] ^= 1;
		Ans[l] = S[l];
		fxd[l] = 1;
	}
	answer(Ans, D);
}

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