| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1106049 | RKHTM | Robots (IOI13_robots) | C++17 | 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 "robots.h"
using namespace std;
#define yasuho ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
typedef long long ll;
const ll MOD = 1e9+7;
int putaway(int a, int b, int t, int x[], int y[], int weight[], int size[]){
int mxa=LLONG_MIN, mxb=LLONG_MIN;
for(int i=0; i<a; i++) mxa = max(mxa, x[i]);
for(int i=0; i<b; i++) mxb = max(mxb, y[i]);
for(int i=0; i<t; i++){
if(weight[i]<mxa or size[i]<mxb) continue;
return -1;
}
ll l=1, r=t, m/*time*/;
while(l<=r){
m = (l+r)/2;
// cout << l << ' ' << r << ' ' << m << endl;
priority_queue<pair<ll, ll>> all; // {-weight, size}
for(int i=0; i<t; i++) all.push({-1*weight[i], size[i]});
priority_queue<pair<ll, ll>> in; // {size, weight}
for(int i=0; i<a; i++){
while(not all.empty() and all.top().first*-1<x[a]){
in.push({all.top().second, all.top().first*-1});
all.pop();
}
for(int j=1; j<=m and not in.empty(); j++) in.pop();
}
priority_queue<pair<ll, ll>> jackpot; // {-size, weight}
while(not all.empty()){
jackpot.push({all.top().second*-1, all.top().first*-1});
all.pop();
}
while(not in.empty()){
jackpot.push({in.top().first*-1, in.top().second});
in.pop();
}
for(int i=0; i<b; i++){
for(int j=1; j<=m and not jackpot.empty(); j++){
if(jackpot.top().first*-1>=size[i]) break;
jackpot.pop();
}
}
if(jackpot.empty()) r=m-1;
else l=m+1;
}
return l;
}
void solve(){
int a, b, t; cin >> a >> b >> t;
int x[a], y[b], weight[t], size[t];
for(int i=0; i<a; i++) cin >> x[i];
for(int i=0; i<b; i++) cin >> y[i];
for(int i=0; i<t; i++) cin >> weight[i];
for(int i=0; i<t; i++) cin >> size[i];
cout << putaway(a, b, t, x, y, weight, size);
return;
}
int main(){
yasuho // remove for interactive problem
ll t;
t = 0;
//cin >> t;
while(t--) solve();
}