제출 #764652

#제출 시각아이디문제언어결과실행 시간메모리
764652lalig777동굴 (IOI13_cave)C++14
12 / 100
142 ms444 KiB
#include "cave.h" #include <iostream> #include <vector> #include <cstring> using namespace std; int N; /*int tryCombination(int S[]){ for (int i=0; i<N; i++) cout<<S[i]<<" "; cout<<endl; int a; cin>>a; return a; } void answer(int S[], int D[]){ for (int i=0; i<N; i++) cout<<S[i]<<" "; cout<<endl; for (int i=0; i<N; i++) cout<<D[i]<<" "; cout<<endl; return; }*/ void exploreCave(int N) { int S[N]={0}; int ans[N]; memset(ans, -1, sizeof ans); int D[N]={0}; for (int i=0; i<N; i++){ int l=0, r=N-1, m, u; for (int j=0; j<N; j++){ if (ans[j]!=-1) S[j]=ans[j]; else S[j]=0; } int res=tryCombination(S); m = l + (r-l)/2; for (int j=0; j<=m; j++){ if (ans[j]!=-1) S[j]=ans[j]; else S[j]=1; } int res2=tryCombination(S); if (res2==res and res==i) { u=1; l=m+1; } else if (res2==res and res!=i) { u=0; l=m+1; } else if (res2!=res and res==i){ u=1; r=m; } else{ u=0; r=m; } /*cout << "pre binary search\n"; cout << "ans"; for (int k: ans) cout << ' ' << k; cout << '\n'; cout << "S"; for (int k: S) cout << ' ' << k; cout << '\n'; cout << "i " << i << endl;*/ while(l<=r){ m = l + (r-l)/2; if (l==r) { D[l]=i; ans[l]=u; /*cout << l << ' ' << r << '\n'; cout << "i " << i << endl; cout << "ans"; for (int k: ans) cout << ' ' << k; cout << '\n'; cout << "D"; for (int k: D) cout << ' ' << k; cout << '\n';*/ break; } for (int j=l; j<=m; j++){ if (ans[j]!=-1) S[j]=ans[j]; else S[j]=u; }for (int j=m+1; j<=r; j++){ if (ans[j]!=-1) S[j]=ans[j]; else S[j]= 1-u; } res=tryCombination(S); if (res==i) l=m+1; else r=m; /*cout << "i " << i << endl; cout << l << ' ' << r << '\n'; cout << "ans"; for (int k: ans) cout << ' ' << k; cout << '\n'; cout << "S"; for (int k: S) cout << ' ' << k; cout << '\n';*/ } }answer(ans, D); } /*int main(){ cin>>N; exploreCave(N); return 0; }*/
#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...