제출 #482659

#제출 시각아이디문제언어결과실행 시간메모리
482659gmyu동굴 (IOI13_cave)C++14
100 / 100
321 ms460 KiB
/* ID: USACO_template LANG: C++ PROG: https://oj.uz/problem/view/IOI13_cave */ #include <iostream> //cin , cout #include <fstream> //fin, fout #include <stdio.h> // scanf , pringf #include <cstdio> #include <algorithm> // sort , stuff #include <stack> // stacks #include <queue> // queues #include <map> #include <string> #include <string.h> #include <set> using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; /// adjlist without weight typedef vector<pii> vii; /// adjlist with weight typedef vector<pair<int,pii>> vpip; /// edge with weight typedef long long ll; #define mp make_pair #define ff first #define ss second #define pb push_back #define sz(x) (int)(x).size() const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; // const ll INF = 1e18; // #define MAXV 300007 #define MAXE 100007 bool debug=false; /* int tryCombination(int S[]){ int s0[] ={1,1,1,0}, d0[] = {3,1,0,2}; int ok[] ={0,0,0,0}; for(int i=0;i<4;i++) { if(S[i]==s0[i]) ok[d0[i]] = 1; } for(int i=0;i<4;i++) if(!ok[i]) return i; return -1; } void answer(int s[], int d[]) { cout << "final answer" << endl; printKey(s,d,4); } */ void printKey(int s[], int d[], int N) { cout << "On/off "; for(int i=0; i<N; i++) cout << s[i] << " "; cout << endl << "Door "; for(int i=0; i<N; i++) cout << d[i] << " "; cout << endl; } #include "cave.h" void exploreCave(int N) { int corSet[N],corDoor[N]; if(N==1) { corDoor[0] = 0; corSet[0] = 1; if(tryCombination(corSet)==0) corSet[0] = 0; answer(corSet, corDoor); } for(int i=0;i<N;i++) { corSet[i]=0; corDoor[i]=-1;} for(int cur = 0; cur <N; cur++) { int l=0, r=N-1; for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = 0; int ans = tryCombination(corSet); int key = 1; while(l<r) { if(debug) printKey(corSet, corDoor, N); if(debug) cout << " .. for door " << cur << ": " << ans << ":" << l << " " << r ; // make sure the door is open if(ans==-1 || ans>cur) { // door opened, as I wanted } else { // the flip will make the door open for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i]; if(debug) { cout << " open " << tryCombination(corSet) << "; " << endl; printKey(corSet, corDoor, N); } } // try half of it to close this door int m = (l+r)/2; for(int i=l; i<=m; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i]; ans = tryCombination(corSet); if(ans == cur) { // successfully closed it. The right door is in this half r=m; key = !corSet[l]; } else { l=m+1; key = corSet[l]; } if(debug) cout << " ==> " << ans << ":" << l << " " << r << endl; } corDoor[l] = cur; corSet[l] = key; if(debug) { cout << "temp answer -- " << endl; printKey(corSet, corDoor, N); } } if(debug) printKey(corSet, corDoor, N); answer(corSet, corDoor); } /* int main() { debug = false; ios_base::sync_with_stdio(false); cin.tie(0); exploreCave(4); if(debug) cout << endl << "EOL" << endl; } */
#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...