제출 #607678

#제출 시각아이디문제언어결과실행 시간메모리
607678jairRS동굴 (IOI13_cave)C++17
100 / 100
168 ms592 KiB
#include "cave.h" #include <bits/stdc++.h> #define all(s) s.begin(), s.end() using namespace std; using vi = vector<int>; const int MAXN = 5'000; int switches[MAXN]; // door triggered by switchID int door[MAXN]; int gN; // returns N instead of -1 when all doors are open int getLastDoor() { int lastDoor = tryCombination(switches); if (lastDoor == -1) lastDoor = gN; return lastDoor; } void flipSwitches(int i, int j, vi &ids) { for (int k = i; k <= j; k++) switches[ids[k]] = !switches[ids[k]]; } void exploreCave(int N) { gN = N; vi unassignedSwitches; for (int i = 0; i < N; i++) unassignedSwitches.push_back(i); // doors up to curDoor EXCEPT curDoor are open for (int curDoor = 0; curDoor < N; curDoor++) { int doorOpen = getLastDoor() > curDoor; int respSwitch; int lo = 0, hi = unassignedSwitches.size() - 1; while (lo < hi) { int mid = (lo + hi) / 2; flipSwitches(lo, mid, unassignedSwitches); int lastDoor = getLastDoor(); bool check = false; if (doorOpen) { if (lastDoor == curDoor) check = true; } else if (lastDoor > curDoor) check = true; if (check) hi = mid; else lo = mid + 1; flipSwitches(lo, mid, unassignedSwitches); } respSwitch = unassignedSwitches[lo]; unassignedSwitches.erase(find(all(unassignedSwitches), respSwitch)); door[respSwitch] = curDoor; if (!doorOpen) switches[respSwitch] = !switches[respSwitch]; } answer(switches, door); }
#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...