제출 #296848

#제출 시각아이디문제언어결과실행 시간메모리
296848Haunted_Cpp동굴 (IOI13_cave)C++17
100 / 100
987 ms888 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 5000 + 5; int conn[MAX_N], optimal[MAX_N]; int estado[MAX_N], as[MAX_N]; void exploreCave(int n) { auto ask = [&](const vector<int> &arr) { for (int i = 0; i < n; i++) { as[i] = arr[i]; } int res = tryCombination(as); return (res == -1 ? n : res); }; vector<int> sw_state(n, -1); vector<int> sw_conn(n, -1); vector<int> state(n, 0); int current_door = ask(state); vector<int> valid_switch(n); iota(valid_switch.begin(), valid_switch.end(), 0); for (int porta_atual = 0; porta_atual < n; porta_atual++) { int lo = 0; int hi = (int) valid_switch.size(); while(lo < hi) { const int mid = lo + (hi - lo) / 2 + 1; vector<int> arr(n); for (int i = 0; i < n; i++) { arr[i] = estado[i]; } for (int i = 0; i < mid; i++) { const int s_i = valid_switch[i]; arr[s_i] = 1; } int nxt_door = ask(arr); if (current_door > porta_atual) { if (nxt_door == porta_atual) { hi = mid - 1; } else { lo = mid; } } else { if (nxt_door > porta_atual) { hi = mid - 1; } else { lo = mid; } } } sw_conn[porta_atual] = valid_switch[hi]; sw_state[porta_atual] = (current_door > porta_atual ? 0 : 1); valid_switch.erase(find(valid_switch.begin(), valid_switch.end(), valid_switch[hi])); estado[sw_conn[porta_atual]] = sw_state[porta_atual]; int res = tryCombination(estado); current_door = (res == -1 ? n : res); // cout << "BOTAO DA PORTA: " << porta_atual << ' ' << sw_conn[porta_atual] << ' ' << sw_state[porta_atual] << '\n'; conn[sw_conn[porta_atual]] = porta_atual; optimal[sw_conn[porta_atual]] = sw_state[porta_atual]; } answer(optimal, conn); }
#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...