| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 503012 | kevin | 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 "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl cout<<"\n"
#define s second
#define f first
#define all(x) x.begin(), x.end()
#define ca(v) for(auto i:v) cout<<i<<" ";
bool solve(int m, vector<int> &X, vector<int> &Y, vector<pair<int, int>> &T){
priority_queue<pair<int, int>> q;
int r = 0;
for(int x : X){
while(r < T.size() && T[r].f < x) {q.push({T[r+1].s, T[r+1].f}); r++;}
int rem = m;
while(rem && q.size()) {
q.pop();
rem--;
}
}
vector<int> nT;
for(int i=r; i<T.size(); i++) nT.push_back(T[i].s);
while(q.size()) { nT.push_back(q.top().f); q.pop(); }
sort(all(nT));
r = 0;
for(int x:Y){
int rem = m;
while(rem && r < nT.size() && x > nT[r]){
rem--;
r++;
}
}
return r == nT.size();
}
int putaway(int A, int B, int N, int x[], int y[], int w[], int s[]){
vector<int> X, Y;
for(int i=0; i<A; i++) X.push_back(x[i]);
for(int i=0; i<B; i++) Y.push_back(y[i]);
sort(all(X));
sort(all(Y));
int ans = N+1;
int l = 1;
int r = N;
vector<pair<int, int>> T;
for(int i=0; i<N; i++) T.push_back({w[i], s[i]});
sort(all(T));
while(l <= r){
int m = (l + r) / 2;
if(solve(m, X, Y, T)){
ans = m;
r = m-1;
}
else l = m+1;
}
if(ans == N+1) return -1;
return ans;
}