# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
4293 |
2013-09-11T17:34:03 Z |
cki86201 |
Robots (IOI13_robots) |
C++ |
|
0 ms |
21136 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 |
Incorrect |
0 ms |
21136 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
21136 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21136 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21136 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21136 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21136 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21136 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21136 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |