Submission #220342

#TimeUsernameProblemLanguageResultExecution timeMemory
220342XmtosXRobots (IOI13_robots)C++17
76 / 100
953 ms65540 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; const int N=1e6; pair<int,int> p[N]; multiset<pair<int,int> > s1; multiset<pair<int,int> > ::iterator it; multiset<int> s[11]; int cur[50004]; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { for (int i=0;i<T;i++) { p[i]={W[i],S[i]}; } sort(p,p+T); sort(X,X+A); reverse(p,p+T); reverse(X,X+A); int low=1,high=T,ans=-1,mid,last=0,lol=0; s1.insert(make_pair(2e9+1,0)); while (low<=high) { if (!s[lol].empty()) s[lol].clear(); for (int i=0;i<B;i++) { if (cur[i]==last) s1.insert(make_pair(Y[i],i)); cur[i]=0; } mid= (low+high)/2; last=mid; long long x=0; int cnt=0; bool yes=true; for (int i=0;i<T;i++) { while (cnt<A&&p[i].first<X[cnt]) { cnt++; x+=mid; } s[lol].insert(p[i].second); if (!x) { if (s[lol].empty()) { yes=false; break; } it= s1.lower_bound(make_pair(*s[lol].begin(),B)); if ((*it).first==2e9+1) { yes=false; break; } pair<int,int> P= *it; cur[P.second]++; if (cur[P.second]==mid) { s1.erase(it); } s[lol].erase(s[lol].begin()); } else { x--; } } lol++; lol%=10; if (yes) { ans=mid; high=mid-1; } else low=mid+1; } return ans; }
#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...