| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4294 |
2013-09-11T17:34:49 Z |
cki86201 |
Robots (IOI13_robots) |
C++ |
|
1532 ms |
27284 KB |
#include "robots.h"
#include<algorithm>
#include<queue>
using namespace std;
const int MX = 1000010;
bool comp(const int *a,const int *b){return *a<*b;}
int *ord[MX];
int wn[MX],sn[MX];
int A,B,T;
typedef pair<int,int> P;
priority_queue <P>pq;
bool solve(int x)
{
while(!pq.empty())pq.pop();
int i,n;
for(i=n=0;i<T;i++){
while(*ord[i]!=n){
int cnt=x;
while(!pq.empty()&&cnt--)pq.pop();
n++;
}
pq.push(P(sn[ord[i]-wn],*ord[i]));
}
while(A!=n){
int tm=x;
while(!pq.empty()&&tm--)pq.pop();
n++;
}
int cnt=0;
while(!pq.empty()){
P tmp=pq.top();pq.pop();
cnt++;
if(cnt>(long long)(B-tmp.first)*x)return false;
}
return true;
}
int putaway(int A_, int B_, int T_, int X[], int Y[], int W[], int S[]) {
A=A_,B=B_,T=T_;
sort(X,X+A);
sort(Y,Y+B);
int i,n=0;
for(i=0;i<T;i++)ord[i]=W+i;
sort(ord,ord+T,comp);
for(i=0;i<T;i++){
while(n!=A&&*ord[i]>=X[n])n++;
wn[ord[i]-W]=n;
}
for(i=0;i<T;i++)ord[i]=S+i;
sort(ord,ord+T,comp);
for(i=n=0;i<T;i++){
while(n!=B&&*ord[i]>=Y[n])n++;
sn[ord[i]-S]=n;
}
for(i=0;i<T;i++)ord[i]=wn+i;
sort(ord,ord+T,comp);
int st=T/(A+B),en=T,mi,ans=-1;
while(st<=en){
int mi=(st+en)>>1;
if(solve(mi))ans=mi,en=mi-1;
else st=mi+1;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
1216 ms |
27284 KB |
Output is correct |
| 5 |
Correct |
1280 ms |
27284 KB |
Output is correct |
| 6 |
Correct |
72 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
800 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
1128 ms |
27284 KB |
Output is correct |
| 9 |
Correct |
1268 ms |
27284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 16 |
Correct |
16 ms |
21136 KB |
Output is correct |
| 17 |
Correct |
20 ms |
21136 KB |
Output is correct |
| 18 |
Correct |
12 ms |
21268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 10 |
Correct |
1188 ms |
27284 KB |
Output is correct |
| 11 |
Correct |
1308 ms |
27284 KB |
Output is correct |
| 12 |
Correct |
72 ms |
21136 KB |
Output is correct |
| 13 |
Correct |
808 ms |
21136 KB |
Output is correct |
| 14 |
Correct |
1148 ms |
27284 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 16 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 17 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 18 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 19 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 20 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 21 |
Correct |
16 ms |
21136 KB |
Output is correct |
| 22 |
Correct |
1228 ms |
27284 KB |
Output is correct |
| 23 |
Correct |
1216 ms |
27284 KB |
Output is correct |
| 24 |
Correct |
1112 ms |
27284 KB |
Output is correct |
| 25 |
Correct |
1028 ms |
22676 KB |
Output is correct |
| 26 |
Correct |
1136 ms |
27284 KB |
Output is correct |
| 27 |
Correct |
1208 ms |
24212 KB |
Output is correct |
| 28 |
Correct |
1532 ms |
24212 KB |
Output is correct |
| 29 |
Correct |
1244 ms |
27284 KB |
Output is correct |
