Submission #308826

#	Time	Username	Problem	Language	Result	Execution time	Memory
308826		LifeHappen__	Robots (IOI13_robots)	C++14	100 / 100	1078 ms	65536 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
using ii=pair<int,int>;
using ll=long long;
using ull=unsigned long long;

const int N=1e6+5;
const int M=5e4+5;
vector<int> query[2*N];

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]) {
   sort(Y, Y+B);
   sort(X, X+A);
   int n=A+B;
   forinc(i,0,T-1){
      int u=upper_bound(X,X+A,W[i])-X;
      int v=upper_bound(Y,Y+B,S[i])-Y;
      v=B-1-v;
      v+=A;
      query[u].pb(v);
      if(u>v) return -1;
   }
   auto chk=[&](int val){
      priority_queue<int,vector<int>,greater<int>> h;
      forinc(i,0,n-1){
         forv(v,query[i]) h.push(v);
         forinc(j,1,val){
            if(h.empty()) break;
            if(h.top()<i) return false;
            h.pop();
         }
      }
      return h.empty();
   };
   if(!chk(T)) return -1;
   int l=1, r=T, ret=-1;
   while(l<=r){
      int mid=l+(r-l)/2;
      if(chk(mid)) ret=mid, r=mid-1;
      else l=mid+1;
   }
   return ret;
}
/**
int n,m,k;
int a[M],b[M],c[N],d[N];

int32_t main(){
   fasty;

   #define task "robot"
   if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
   }

   cin>>n>>m>>k;
   forinc(i,0,n-1) cin>>a[i];
   forinc(i,0,m-1) cin>>b[i];
   forinc(i,0,k-1) cin>>c[i-1]>>d[i-1];
   cout<<putaway(n,m,k,a,b,c,d);
}
*/

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10