Submission #282911

#	Time	Username	Problem	Language	Result	Execution time	Memory
282911		themax23	Cave (IOI13_cave)	C++17	0 / 100	2087 ms	1496 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x << ": " << x << '\n';
using namespace std;

int n;
//const int NMAX = 5000;
//int S[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) {
	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) {
	n = N;
	int S[N] = {0}, D[N] = {0}, T[N] = {0};
	deb(n);
//	for(int i = 0; i < N; ++i)
//		cerr << D[i] << ' ';
//	cerr << '\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,T);
		
		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;
		
	}
	/*	cerr << "D: ";
		for(int i = 0; i < N; ++i){
		cerr << D[i] << ' ';
		}
	cerr << '\n';*/
	//int klk[4] = {0,0,1,0};
	//int check = tryCombination(klk);
	//deb(check);
	answer(T,D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:65:8: warning: unused variable 'side' [-Wunused-variable]
   65 |   char side = 'L';
      |        ^~~~
cave.cpp:57:6: warning: unused variable 'S' [-Wunused-variable]
   57 |  int S[N] = {0}, D[N] = {0}, T[N] = {0};
      |      ^

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