제출 #283506

#제출 시각아이디문제언어결과실행 시간메모리
283506themax23동굴 (IOI13_cave)C++17
0 / 100
432 ms592 KiB
#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], 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)); 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 = (N+1) / 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 = (N+1) / 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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...