제출 #738657

#제출 시각아이디문제언어결과실행 시간메모리
738657BidoTeima동굴 (IOI13_cave)C++17
100 / 100
790 ms972 KiB
#include "cave.h" #include <bits/stdc++.h> int n; int pos[5000]; int door[5000]; int dnc(int l, int r, bool b, int target){ if(l == r) return l; int mid = (l + r) >> 1; // first check if it's in [l, mid] int s[n]; for(int i = 0; i < n; i++){ if(pos[i] != -1){ s[i] = pos[i]; } else if(l <= i && i <= mid){ s[i] = b; } else{ s[i] = !b; } } int res = tryCombination(s); if(res <= target && res != -1){ return dnc(mid + 1, r, b, target); } return dnc(l, mid, b, target); } void exploreCave(int N) { n = N; memset(pos, -1, sizeof(pos)); for(int i = 0; i < n; i++){ int s[n]; for(int j = 0; j < n; j++){ if(pos[j] != -1)s[j] = pos[j]; else s[j] = 0; } int res = tryCombination(s); bool b = 0; if(res <= i && res != -1){ b = 1; } int sw = dnc(0, n-1, b, i); pos[sw] = b; door[sw] = i; } answer(pos, 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...