| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 308825 | LifeHappen__ | Robots (IOI13_robots) | C++14 | 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 <bits/stdc++.h>
#include "robot.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);
}
*/