Submission #283511

#	Time	Username	Problem	Language	Result	Execution time	Memory
283511		themax23	Cave (IOI13_cave)	C++17	100 / 100	597 ms	640 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);
		/*cerr << "First Combination: ";
		for(int it = 0; it < n; ++it)
			cerr << test[it] << ' ';*/
		
		bool cur_door_state = check_state(first_closed_door,cur_door); // 0 = open, 1 = closed
		//cerr << ", cur_door_state: " << cur_door_state << '\n';
		//deb(first_closed_door);
		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;
			}
			/*cerr << "test: ";
			for(int it = 0; it < n; ++it)
				cerr << test[it] << ' ';
			cerr << '\n';*/
			first_closed_door = tryCombination(test);
			//deb(first_closed_door);
			bool new_cur_door_state = check_state(first_closed_door,cur_door);
			//cerr << "cur_door_state, new_cur_door_state: " <<cur_door_state << ' ' << new_cur_door_state << '\n';
			if(cur_door_state == new_cur_door_state)
				{find_switch += "R"; start_idx += k;}
			else 
				{find_switch += "L";} 
			k /= 2;
		}
		//deb(find_switch);
		int switch_idx = 0;
		int f = extra / 2;
		for(char x : find_switch){
			if(x == 'R') switch_idx += f;
			f /=2;
		}
		//cerr << "find_switch, switch_idx: " <<find_switch << ' ' << switch_idx << '\n';
		D[switch_idx] = cur_door;
		if(cur_door_state == 1) S[switch_idx] = 1;
		else S[switch_idx] = 0;
	/*	cerr << "D: ";
		for(int it = 0; it < n; ++it)
				cerr << D[it] << ' ';
		cerr << '\n';
		cerr << "S: ";
		for(int it = 0; it < n; ++it)
			cerr << S[it] << ' ';
		cerr << '\n';*/
		for(int l=0; l<n; ++l){
			if(S[l] == -1) 
				test[l] = 0;
			else
				test[l] = S[l];
			}
		
	}
	/*int klk[4] = {0,0,1,0};
	int check = tryCombination(klk);
	deb(check);*/
	answer(S,D);
}

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