Submission #1088860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088860		Alihan_8	Cave (IOI13_cave)	C++17	12 / 100	311 ms	660 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using namespace std;

int qry(vector <int> S){
	int n = S.size(), t[n];
	
	for ( int i = 0; i < n; i++ ) t[i] = S[i];
	
	int x = tryCombination(t);
	
	if ( x == -1 ) x = n;
	
	return x;
}

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

void exploreCave(int n){
	vector <int> p(n), s(n), t;
	
	for ( int i = 0; i < n; i++ ) t.push_back(i);
	
	for ( int i = 0; i < n; i++ ){
		int m = t.size();
		
		for ( auto &j: t ) s[j] = 0;
		
		int x = 0;
		
		if ( qry(s) <= i ) x = 1;
		
		int l = 0, r = m - 1;
		
		while ( l < r ){
			int md = (l + r) / 2;
			
			for ( int j = 0; j < m; j++ ){
				if ( j <= md ) s[t[j]] = x;
				else s[t[j]] = x ^ 1;
			}
			
			if ( qry(s) <= i ){
				l = md + 1;
			} else r = md;
		}
		
		s[i] = x, p[i] = t[l];
		
		vector <int> nxt;
		
		for ( int j = 0; j < m; j++ ){
			if ( j != l ) nxt.push_back(t[j]);
		} swap(t, nxt);
	}
	
	vector <int> iv(n);
	
	for ( int i = 0; i < n; i++ ){
		iv[p[i]] = i;
	}
	
	ans(s, iv);
}

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