Submission #283512

#	Time	Username	Problem	Language	Result	Execution time	Memory
283512		themax23	Cave (IOI13_cave)	C++17	100 / 100	617 ms	760 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x << ": " << x << '\n';
using namespace std;
int N;
const int NMAX = 8192;
int S[NMAX], D[NMAX], test[NMAX];

bool check_state(int first_closed_door, int idx){
	if(first_closed_door == -1) return 0;
	if(first_closed_door > idx) return 0;
	return 1;
}

void exploreCave(int n) {
	N = n;
	memset(S,-1,sizeof(S));
	int t = ceil(log2(N));
	int extra = (1 << t);
	for(int i = N; i < extra; ++i){
		D[i] = i;
		S[i] = 0;
	}
	for(int cur_door = 0; cur_door < n; ++cur_door){ 
		int first_closed_door = tryCombination(test);		
		bool cur_door_state = check_state(first_closed_door,cur_door); // 0 = open, 1 = closed
		int k = (extra) / 2, start_idx = 0;
		string find_switch = "";
		for(int i = 0; i < t; ++i){
			for(int l=0; l<n; ++l){
				if(S[l] == -1) 
					test[l] = 0;
				else
					test[l] = S[l];
			}
			for(int indx = 0; indx < k; ++indx){
				if(S[start_idx + indx] == -1)
					test[start_idx + indx] = 1;
			}
			first_closed_door = tryCombination(test);
			bool new_cur_door_state = check_state(first_closed_door,cur_door);
			if(cur_door_state == new_cur_door_state)
				{find_switch += "R"; start_idx += k;}
			else 
				{find_switch += "L";} 
			k /= 2;
		}
		int switch_idx = 0;
		int f = extra / 2;
		for(char x : find_switch){
			if(x == 'R') switch_idx += f;
			f /=2;
		}
		D[switch_idx] = cur_door;
		if(cur_door_state == 1) S[switch_idx] = 1;
		else S[switch_idx] = 0;
		for(int l=0; l<n; ++l){
			if(S[l] == -1) 
				test[l] = 0;
			else
				test[l] = S[l];
			}
	}
	answer(S,D);
}

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