Submission #282916

#	Time	Username	Problem	Language	Result	Execution time	Memory
282916		themax23	Cave (IOI13_cave)	C++17	0 / 100	404 ms	464 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x << ": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;

int n;
const int NMAX = 5000;
int T[NMAX], D[NMAX];
bool check_state(int* test, int idx){
	int first = tryCombination(test);
	
/*	cerr << "test: ";
	for(int i = 0; i < n; ++i)
		cerr << test[i] << ' ';
	cerr << '\n';*/
	
	//deb(idx); deb(first);
	//cerr << "first, idx: "<< first << ' ' << idx << '\n';
	if(first == -1) return false;
	if(first > idx) return false;
	return true;
}

string nextCombination( int idx, bool state) {
	int t = ceil(log2(n));
	string find = "";
	int k = (n+1) / 2;
	//deb(t);
	int start_idx = 0;
    for(int i = 0; i < t; ++i){
		int test[n];
		for(int l=0; l<n; ++l) test[l] = T[l];
		
		for(int indx = 0; indx < k; ++indx){
			test[start_idx + indx] = 1;
		}
		
		//deb(start_idx); deb(k);
		//cerr << "test: ";
		//for(int it = 0; it < n; ++it)
		//	cerr << test[it] << ' ';
		//cerr << '\n';
		
		bool new_state = check_state(test,idx);
		//deb(state); deb(new_state);
		if(state != new_state) find += "L";
		else {find += "R"; start_idx += k;}
		//deb(k);
		k /= 2;
	}
	//deb(find);
	return find;
}

void exploreCave(int N) {
	ios;
	n = N;
	//int D[N] = {0}, T[N] = {0};
	//deb(n);
	for(int i = 0; i < N; ++i){
		bool state = check_state(T,i); // 0 = open, 1 = closed
		char side = 'L';
		//deb(state);
		string ans = nextCombination(i,state);
		int door_idx = 0;
		int f = (N+1) / 2;
		for(char x : ans){
			if(x == 'R') door_idx += f;
			f /=2;
		}
		D[door_idx] = i;
		T[door_idx] = state;
		
	}
	answer(T,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:63:8: warning: unused variable 'side' [-Wunused-variable]
   63 |   char side = 'L';
      |        ^~~~

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