제출 #995942

#제출 시각아이디문제언어결과실행 시간메모리
995942daffuwu동굴 (IOI13_cave)C++14
100 / 100
224 ms592 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; int s[5069], d[5069], unk[5069], lo, hi, mi; int conv(int x) { if (x == -1) return 5001; return x; } void exploreCave(int n) { int i, j, m; //mulai dari 000000 //d[i] --> switch i door apa //unk --> array yang buat switch apa aja yang belum tahu connect ke door apa (unknown) for (i=0; i<=n-1; i++) s[i] = 0; for (i=0; i<=n-1; i++) d[i] = -1; //tentuin tiap door dari 0, 1, ... n-1 switchnya apa for (i=0; i<=n-1; i++) { for (j=0, m=-1; j<=n-1; j++) { if (d[j] == -1) unk[++m] = j; } if (tryCombination(s) != i) { //flip semua switch unkwon, karena switch unknown connect ke door yang indeksnya >=i for (j=0; j<=m; j++) s[unk[j]] ^= 1; } //pasti switch yang connect ke door i ketutup boz (tryCombination(s) == i) //tinggal daffanandabinser mainin switch yang unknown, switch mana nich yang connect ke door i for (lo=0, hi=m; lo<=hi; ) { mi = (lo+hi)/2; for (j=0; j<=mi; j++) s[unk[j]] ^= 1; if (conv(tryCombination(s))>i) hi = mi-1; //yang paling kiri dan door i kebuka adalah switchnya :D else lo = mi+1; for (j=0; j<=mi; j++) s[unk[j]] ^= 1; } s[unk[hi+1]] ^= 1; d[unk[hi+1]] = i; } 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...