| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 2969 |
2013-08-19T09:40:09 Z |
cki86201 |
Robots (IOI13_robots) |
C++ |
|
0 ms |
32080 KB |
#include "robots.h"
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=0x7fffffff;
struct robot{int w,s,wn,sn,n;bool operator<(const robot &l)const{return w!=l.w?w<l.w:s>l.s;}}inp[1000010];
int p[50010],q[50010],N,A,B;
int np[50010],nq[50010],in;
int check[1000010];
vector <robot> Ww[50010],Ss[50010];
vector <int> WL,SL;
bool comp1(const robot &a,const robot &b){return a.s!=b.s?a.s<b.s:a.w>b.w;}
bool comp2(const robot &a,const robot &b){return a.wn!=b.wn?a.wn<b.wn:a.sn>b.sn;}
bool comp3(const robot &a,const robot &b){return a.sn!=b.sn?a.sn<b.sn:a.wn>b.wn;}
bool solve(int x)
{
WL.clear();SL.clear();
int i,C=0;
for(i=1;i<=A;i++)np[i]=0;
for(i=1;i<=B;i++)nq[i]=0;
for(i=1;i<=A;i++){
int u,j=i;
for(u=1;u<=x;){
if(np[j]==Ww[j].size()){
if(WL.empty())break;
else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
}
check[Ww[j][np[j]].n]=in;
np[j]++;
C++;
if(C==N)return true;
if(np[j]==Ww[j].size()){
if(WL.empty())break;
else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
}
if(u==x&&j==i&&np[j]!=Ww[j].size())WL.push_back(i);
u++;
}
}
for(i=1;i<=B;i++){
int u,j=i;
for(u=1;u<=x;){
if(nq[j]==Ss[j].size()){
if(SL.empty())break;
else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
}
if(check[Ss[j][nq[j]].n]==in){nq[j]++;continue;}
check[Ss[j][nq[j]].n]=in;
nq[j]++;
C++;
if(C==N)return true;
if(nq[j]==Ss[j].size()){
if(SL.empty())break;
else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
}
if(u==x&&j==i&&nq[j]!=Ss[j].size())SL.push_back(i);
u++;
}
}
return false;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i;
for(i=1;i<=A;i++){p[i]=X[i-1]-1;}sort(p+1,p+1+A);p[A+1]=INF;
for(i=1;i<=B;i++){q[i]=Y[i-1]-1;}sort(q+1,q+1+B);q[B+1]=INF;
for(i=1;i<=T;i++){inp[i].w=W[i];inp[i].s=S[i];inp[i].n=i;}
sort(inp+1,inp+1+T);
int c=1;
for(i=1;i<=T;i++){
while(inp[i].w>p[c])c++;
inp[i].wn=c;
}
sort(inp+1,inp+1+T,comp1);
for(i=c=1;i<=T;i++){
while(inp[i].s>q[c])c++;
inp[i].sn=c;
if(c>B&&inp[i].wn>A){printf("-1");return 0;}
}
sort(inp+1,inp+1+T,comp2);
for(i=1;i<=T;i++)Ww[inp[i].wn].push_back(inp[i]);
sort(inp+1,inp+1+T,comp3);
for(i=1;i<=T;i++)Ss[inp[i].sn].push_back(inp[i]);
int st=T/(A+B),en=T,mi,ans;
while(st<=en){
mi=(st+en)>>1;++in;
if(solve(mi)){
ans=mi;
en=mi-1;
}
else st=mi+1;
}printf("%d",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
