This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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';
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |