#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
long long inf = 20000000000007LL;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//int putaway(int A, int B, int T, vector <int> X, vector <int> Y, vector <int> W, vector <int> S) {
vector <pair <int, int>> save;
for (int i = 0; i < T; i++) {
save.push_back(make_pair(W[i], S[i]));
}
sort(save.begin(), save.end());
long long ans = -1;
long long lo = 1, hi = inf;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
set <pair <int, int>> myset;
for (int i = 0; i < B; i++) {
myset.insert(make_pair(Y[i], i));
}
vector <long long> numbWeak(A, 0), numbSmall(B, 0);
vector <int> notChoose;
for (int i = T - 1; i >= 0; i--) {
set <pair <int, int>>::iterator it = myset.lower_bound(make_pair(save[i].second, B + 10));
if (it != myset.end()) {
numbSmall[(*it).second]++;
if (numbSmall[(*it).second] == mid) {
myset.erase(it);
}
}
else {
notChoose.push_back(i);
}
}
myset.clear();
for (int i = 0; i < A; i++) {
myset.insert(make_pair(X[i], i));
}
reverse(notChoose.begin(), notChoose.end());
vector <int> notChoose2;
for (int i = (int) notChoose.size() - 1; i >= 0; i--) {
set <pair <int, int>>::iterator it = myset.lower_bound(make_pair(save[notChoose[i]].first, A + 10));
if (it != myset.end()) {
numbWeak[(*it).second]++;
if (numbWeak[(*it).second] == mid) {
myset.erase(it);
}
}
else {
notChoose2.push_back(i);
}
}
if (notChoose2.empty() == false) {
lo = mid + 1;
}
else {
ans = mid;
hi = mid - 1;
}
}
return ans;
}
# | 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... |