| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 2964 | cki86201 | Robots (IOI13_robots) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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> W[50010],S[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]==W[j].size()){
if(WL.empty())break;
else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
}
check[W[j][np[j]].n]=in;
np[j]++;
C++;
if(C==N)return true;
if(np[j]==W[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]!=W[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]==S[j].size()){
if(SL.empty())break;
else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
}
if(check[S[j][nq[j]].n]==in){nq[j]++;continue;}
check[S[j][nq[j]].n]=in;
nq[j]++;
C++;
if(C==N)return true;
if(nq[j]==S[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]!=S[j].size())SL.push_back(i);
u++;
}
}
return false;
}
int main()
{
scanf("%d%d%d",&A,&B,&N);
int i;
for(i=1;i<=A;i++){scanf("%d",p+i);p[i]--;}sort(p+1,p+1+A);p[A+1]=INF;
for(i=1;i<=B;i++){scanf("%d",q+i);q[i]--;}sort(q+1,q+1+B);q[B+1]=INF;
for(i=1;i<=N;i++){scanf("%d%d",&inp[i].w,&inp[i].s);inp[i].n=i;}
sort(inp+1,inp+1+N);
int c=1;
for(i=1;i<=N;i++){
while(inp[i].w>p[c])c++;
inp[i].wn=c;
}
sort(inp+1,inp+1+N,comp1);
for(i=c=1;i<=N;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+N,comp2);
for(i=1;i<=N;i++)W[inp[i].wn].push_back(inp[i]);
sort(inp+1,inp+1+N,comp3);
for(i=1;i<=N;i++)S[inp[i].sn].push_back(inp[i]);
int st=N/(A+B),en=N,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;
}