Submission #1088867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088867		Alihan_8	Cave (IOI13_cave)	C++17	100 / 100	477 ms	852 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, q(n);
	
	for ( int i = 0; i < n; i++ ) t.push_back(i);
	
	for ( int i = 0; i < n; i++ ){
		int m = t.size();
		
		for ( auto &x: t ) q[x] = 0; 
		
		int x = 0;
		
		if ( qry(q) <= 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 ) q[t[j]] = x;
				else q[t[j]] = x ^ 1;
			}
			
			if ( qry(q) <= i ){
				l = md + 1;
			} else r = md;
		}
		
		q[t[l]] = 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(q, iv);
}

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