fork(1) download
copy 
  1. #include "robots.h"
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. #define MAXT 1000006
  7. #define MAXN 50004
  8. typedef pair<int,int> pii;
  9.  
  10. static int A,B,T,X[MAXN],Y[MAXN];
  11. static struct TOY{
  12.     int w,s;
  13.     bool operator < (const TOY &ot)const{
  14.         return w < ot.w;
  15.     }
  16. } toy[MAXT];
  17. static priority_queue<pii> que;
  18. static int order[MAXT],chk[MAXT];
  19.  
  20. bool cmp_s(int a,int b){ return toy[a].s<toy[b].s; }
  21.  
  22. int check(int m)
  23. {
  24.     int i,j,k;
  25.     for (i=1;i<=T;i++) chk[i] = 0;
  26.     while (!que.empty()) que.pop();
  27.     for (i=k=1;i<=A;i++){
  28.         while (k <= T && toy[k].w < X[i]){
  29.             que.push(pii(toy[k].s,k));
  30.             k++;
  31.         }
  32.         for (j=0;j<m&&!que.empty();j++){
  33.             chk[que.top().second] = 1;
  34.             que.pop();
  35.         }
  36.     }
  37.     for (i=k=1;i<=B;i++){
  38.         int cnt=0;
  39.         while (k <= T && toy[order[k]].s < Y[i] && cnt < m){
  40.             if (!chk[order[k]]) cnt++, chk[order[k]] = 1;
  41.             k++;
  42.         }
  43.     }
  44.     for (i=1;i<=T;i++) if (!chk[i]) return 0;
  45.     return 1;
  46. }
  47.  
  48. int putaway(int a,int b,int t,int x[],int y[],int W[],int S[])
  49. {
  50.     int i,s,e,m,ans=-1;
  51.     A = a, B = b, T = t;
  52.     for (i=1;i<=A;i++) X[i] = x[i-1];
  53.     for (i=1;i<=B;i++) Y[i] = y[i-1];
  54.     for (i=1;i<=T;i++) toy[i].w = W[i-1], toy[i].s = S[i-1], order[i] = i;
  55.     sort(X+1,X+A+1), sort(Y+1,Y+B+1);
  56.     sort(toy+1,toy+T+1); sort(order+1,order+T+1,cmp_s);
  57.     s = 1, e = T;
  58.     while (s <= e){
  59.         m = (s+e)>>1;
  60.         if (check(m)) e = m-1, ans = m;
  61.         else s = m+1;
  62.     }
  63.     return ans;
  64. }
  65.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Qv54os
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!