Submission #173689

#TimeUsernameProblemLanguageResultExecution timeMemory
173689FieryPhoenixCave (IOI13_cave)C++11
100 / 100
1299 ms640 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <map> #include <queue> #include <set> #include <iomanip> #include <deque> #include <cassert> #include <ctime> #include <cstring> #include <cstdlib> #include <chrono> #include <ctime> #include <random> #include <stack> #include <unordered_set> #include <unordered_map> #include <iterator> #include <climits> #include "cave.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 vector<int>ind; int S[5001],D[5001]; void exploreCave(int N){ for (int i=0;i<N;i++){ S[i]=-1; D[i]=-1; ind.push_back(i); } for (int i=0;i<N;i++){ //figuring out door i now int v[5001]; fill(v,v+N,1); for (int j=0;j<N;j++) if (S[j]!=-1) v[j]=D[j]; int r=tryCombination(v); if (r==-1) r=INF; bool state; if (r>i) state=true; else state=false; int low=0,high=ind.size()-1,mid; while (low<high){ mid=(low+high)/2; int q[5001]; fill(q,q+N,0); for (int j=low;j<=mid;j++) q[ind[j]]=1; for (int j=0;j<N;j++) if (S[j]!=-1) q[j]=D[j]; int res=tryCombination(q); if (res==-1) res=INF; if (res>i){ if (state) high=mid; else low=mid+1; } else{ if (state) low=mid+1; else high=mid; } } S[ind[low]]=i; D[ind[low]]=state; ind.erase(ind.begin()+low); } answer(D,S); }
#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...