| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1753 |
2013-07-14T16:53:58 Z |
ainta |
Robots (IOI13_robots) |
C++ |
|
853 ms |
38736 KB |
#include "robots.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
bool v[1000001],vv[150000];
struct A{
int w,s,x;
bool operator <(const A &q)const{
return w<q.w;
}
}p[1000001];
struct B{
int w,s,x;
bool operator <(const B &p)const{
return s<p.s;
}
}q[1000001];
int E[1000001],F[1000001],SZ=65536;
long long IT[150001];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,be=1,ed=T,M,Res;
sort(X,X+A);
sort(Y,Y+B);
for(i=0;i<T;i++)if((A!=0&&W[i]>=X[A-1])&&(B!=0&&S[i]>=Y[B-1]))break;
if(i!=T)return -1;
for(i=0;i<T;i++){
p[i].w=W[i],p[i].s=S[i],q[i].w=W[i],q[i].s=S[i];
p[i].x=q[i].x=i;
}
sort(p,p+T);
sort(q,q+T);
int c=0;
for(i=0;i<A;i++){
while(c<T && X[i]>p[c].w)
{
E[p[c++].x]=i;
}
}
while(c<T)E[p[c++].x]=i;
c=0;
for(i=0;i<B;i++){
while(c<T && Y[i]>q[c].s)
F[q[c++].x]=i;
}
while(c<T)F[q[c++].x]=i;
int t;
for(i=1;i<150000;i=i*2+1)vv[i]=true;
while(be<=ed){
M=(be+ed+1)>>1;
for(i=0;i<B;i++)IT[SZ+i]=M;
for(i=SZ-1;i>=1;i--)IT[i]=IT[i*2]+IT[i*2+1];
for(i=0;i<T;i++)v[i]=false;
for(i=T-1;i>=0;i--){
t=F[p[i].x]+SZ;
while(IT[t]==0LL){
if(vv[t]){
break;
}
t=(t+1)>>1;
}
if(!IT[t])continue;
while(t<SZ){
t<<=1;
if(!IT[t])t++;
}
while(t){
IT[t]--;
t>>=1;
}
v[p[i].x]=true;
}
c=0;
for(i=T-1;i>=0;i--){
if(!v[p[i].x]){
c++;
if((A-E[p[i].x])*M<c)break;
}
}
if(i==-1)Res=M,ed=M-1;
else be=M+1;
}
return Res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
38736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 4 |
Incorrect |
853 ms |
38736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 10 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 11 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 12 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 13 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 14 |
Correct |
0 ms |
38736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 10 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 11 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 12 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 13 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 14 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 15 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 16 |
Correct |
14 ms |
38736 KB |
Output is correct |
| 17 |
Correct |
12 ms |
38736 KB |
Output is correct |
| 18 |
Correct |
16 ms |
38736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
38736 KB |
Output is correct |
| 10 |
Incorrect |
846 ms |
38736 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
