제출 #476351

#제출 시각아이디문제언어결과실행 시간메모리
476351ponytail동굴 (IOI13_cave)C++17
100 / 100
362 ms456 KiB
#include<bits/stdc++.h> #include "cave.h" using namespace std; void exploreCave(int N) { int S[N],D[N]; bool solved[N]; for(int i=0;i<N;i++){ solved[i]=false; D[i]=-1; } for(int i=0;i<N;i++){ int candidates[N]; int ppt=0; for(int j=0;j<N;j++){ if(solved[j]==false){ S[j]=0; candidates[ppt]=j; ppt++; } } int lb=0, rb=ppt-1; int res=tryCombination(S); int opt=(res==i?1:0); for(int j=0;j<N;j++){ if(solved[j]==false){ S[j]=1-opt; } } res=tryCombination(S); while(lb<rb){ int mid=(lb+rb)/2; for(int j=lb;j<=mid;j++){ if(solved[candidates[j]])continue; S[candidates[j]]=1-S[candidates[j]]; } int now=tryCombination(S); for(int j=lb;j<=mid;j++){ if(solved[candidates[j]])continue; S[candidates[j]]=1-S[candidates[j]]; } if(now!=res){ rb=mid; } else{ lb=mid+1; } } solved[candidates[lb]]=true; S[candidates[lb]]=opt; D[candidates[lb]]=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...