Submission #1195027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195027		ezdp	Cave (IOI13_cave)	C++20	100 / 100	234 ms	592 KiB

cave

#include "cave.h"
#include<vector>
#include<iostream>
using namespace std;

void exploreCave(int N) {
	int opens[N]{}; // i-th lock opens door opens[i];
	int value[N]{}; // i-th lock must be set to value[i] to open door opens[i]
	bool sure[N]{}; // the states for i-th lock are correctly calculated
	int combination[N]{};
	for(int gate = 0; gate < N; gate ++){
		vector<int> cands;
		for(int i = 0; i < N; i ++){
			if(sure[i]) combination[i] = value[i];
			else{
				cands.push_back(i);
				combination[i] = 1;
			}
		}
		int first_locked = tryCombination(combination);
		int key = (first_locked > gate || first_locked == -1);
		int low = 0, high = cands.size() - 1, lock = -1;
		while(low <= high){
			int mid = (low + high) / 2;
			for(int i = 0; i < cands.size(); i ++){
				if(i <= mid) combination[cands[i]] = key;
				else combination[cands[i]] = (key ^ 1);
			}
			int tmp = tryCombination(combination);
			if(tmp > gate || tmp == -1){
				lock = cands[mid];
				high = mid - 1;
			}
			else{
				low = mid + 1;
			}
		}
		opens[lock] = gate;
		value[lock] = key;
		sure[lock] = true;
	}
	answer(value, opens);
}

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