제출 #676564

#제출 시각아이디문제언어결과실행 시간메모리
676564abcdehello동굴 (IOI13_cave)C++17
100 / 100
1010 ms632 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; int n,s[5050],d[5050]; int bs(int cor,int cur){ vector<int> unlinked(0); for (int i=0;i<n;i++) if (d[i]==-1) unlinked.push_back(i); int l=0,r=unlinked.size()-1; while (l!=r){ int m=(l+r)/2; int findstate[5050]; for (int i=0;i<n;i++){ if (d[i]==-1) findstate[i]=cor; else findstate[i]=s[i]; } for (int i=0;i<=m;i++) findstate[unlinked[i]]=cor^1; int door=tryCombination(findstate); if (door==-1) door=n; if (door<=cur) r=m; else l=m+1; } return unlinked[l]; } void exploreCave(int N){ n=N; for (int i=0;i<n;i++) d[i]=-1; for (int i=0;i<n;i++){ int cor,findstate[5050]; for (int j=0;j<n;j++){ if (d[j]==-1) findstate[j]=0; else findstate[j]=s[j]; } int door=tryCombination(findstate); if (door==-1) door=n; if (door>i) cor=0; else cor=1; int sw=bs(cor,i); s[sw]=cor; d[sw]=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...