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>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vi a(A), b(B);
V<pi> c(T);
for(int i = 0; i < A; i++) a[i] = X[i];
for(int i = 0; i < B; i++) b[i] = Y[i];
for(int i = 0; i < T; i++) c[i] = MP(W[i], S[i]);
sort(ALL(a)), sort(ALL(b)), sort(ALL(c), [&] (pi a, pi b) {
return a.S < b.S;
});
auto ok = [&] (int k) { // each people can kill at msot k things
set<int> ms, ms2;
for(int i = A - 1; i >= 0; i--) ms.insert(a[i]);
for(int i = B - 1; i >= 0; i--) ms2.insert(b[i]);
vi cnt(A), cnt2(B);
for(int i = T - 1; i >= 0; i--) {
int x = c[i].F, y = c[i].S;
if(ms.size() && ms.upper_bound(x) != ms.end()) {
auto it = ms.upper_bound(x);
int who = lower_bound(ALL(a), *it) - a.begin();
cnt[who]++;
if(cnt[who] == k) ms.erase(it);
} else {
if(ms2.empty() || ms2.upper_bound(y) == ms2.end())
return false;
auto it = ms2.upper_bound(y);
int who = lower_bound(ALL(b), *it) - b.begin();
cnt2[who]++;
if(cnt2[who] == k) ms2.erase(it);
}
}
return true;
};
int lb = 1, rb = T;
while(lb <= rb) {
int mb = (lb + rb) / 2;
if(ok(mb)) rb = mb - 1;
else lb = mb + 1;
}
if(lb > T) return -1;
return lb;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |