Submission #784731

#TimeUsernameProblemLanguageResultExecution timeMemory
784731bane동굴 (IOI13_cave)C++17
0 / 100
974 ms484 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { /* ... */ vector<int>ne_najdeni; // SWITCHOVI KOI NE SE DOZNAENI vector<int>najdeni; // SWITCHOVI KOI SE DOZNAENI int Match[N]; // SWITCH - > VRATA int P[N]; // SOSTOJBA NA SWITCH for (int i = 0; i < N; i++){ ne_najdeni.push_back(i); } for (int i = 0; i < N; i++){ //PROBUVAME DA JA OTVORIME I-TATA VRATA int S[N]; for (int j : najdeni){ S[j] = P[j]; } //SEGA SME GI OTVORILE SITE VRATI PRED I for (int j : ne_najdeni){ S[j] = 1; } int key = 1; int resp = tryCombination(S); if (resp == i){ //ovaa vrata e seuste zaklucena, znaci se otklucuva so 0 key ^= 1; for (int j : ne_najdeni){ S[j] = key; } } int l = 0, r = (int)ne_najdeni.size() - 1; while(l<=r){ int mid = (l+r) / 2; for (int j = 0 ; j < mid; j++){ S[ne_najdeni[j]] = !key; } for (int j = mid; j < (int)ne_najdeni.size(); j++){ S[ne_najdeni[j]] = key; } resp = tryCombination(S); if (resp == i){ //zaklucena e seuste //prosiri r = mid - 1; }else{ //otklucena e l = mid + 1;//zatesni } } P[l-1]=key; najdeni.push_back(l-1); sort(najdeni.begin(),najdeni.end()); Match[l-1]=i; vector<int>nov; for (int j : ne_najdeni){ if (j == l - 1)continue; nov.push_back(j); } ne_najdeni = nov; sort(ne_najdeni.begin(),ne_najdeni.end()); } answer(P,Match); }
#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...