Submission #409107

#	Time	Username	Problem	Language	Result	Execution time	Memory
409107		Gurban	Cave (IOI13_cave)	C++17	100 / 100	906 ms	920 KiB

cave

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

using ll = long long;

int tr(vector<int>S){
	int ask[(int)S.size()];
	for(int i = 0;i < (int)S.size();i++) ask[i] = S[i];
	return tryCombination(ask);
}

void ans(vector<int>S,vector<int>D){
	int jog[(int)S.size()];
	int d[(int)S.size()];
	for(int i = 0;i < (int)S.size();i++) jog[i] = S[i];
	for(int i = 0;i < (int)D.size();i++) d[i] = D[i];
	answer(jog,d);
}

void exploreCave(int N) {
	vector<pair<int,int>>nw;
	vector<int>vis(N,0);
	vector<int>d(N);
	for(int i = 0;i < N;i++){
		vector<int>ask(N,0);
		for(int j = 0;j < N;j++) ask[j] = 0;	
 		for(auto j : nw) ask[j.first] = j.second;
 		int put = 0;
 		int ind = tr(ask);
 		if(ind == i) put = 1;
 		vector<int>v;
 		for(int j = 0;j < N;j++) if(!vis[j]) v.push_back(j);
 		int l = 0,r = (int)v.size()-1,md;
 		while(l < r){
 			md = (l + r)/2;
 			for(auto j : v) ask[j] = !put;
			for(int j = l;j <= md;j++) ask[v[j]] = put;			
 			int ind = tr(ask);
 			if(ind > i or ind == -1) r = md;
 			else l = md + 1;
 		}
 		d[v[l]] = i;
 		nw.push_back({v[l],put});
 		vis[v[l]] = 1;
 	}
 	vector<int>jog(N);
 	for(auto i : nw) jog[i.first] = i.second;
 	ans(jog,d);
}

// int main(){
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);

// }

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