| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125992 | finalventure | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
// #include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define EPS 1e-9
void init()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
}
// Approach: greedily use the worst robot possible that will make future robots' lives easier
// i.e. use weakest robot and pick up biggest items, and so on
// appear[i] contains all toys that can be picked up by weak robot i
vector<vector<int>> appear;
vector<int> sizes;
bool check(int time)
{
int n = appear.size();
priority_queue<int> pq;
for (int i = 0; i < n - 1; ++i)
{
int nn = appear[i].size();
for (int j = 0; j < nn; ++j)
{
pq.push(appear[i][j]);
}
int pqsz = pq.size();
// We no longer have to consider using this robot again because it's too weak for further toys
for (int j = 0; j < min(time, pqsz); ++j)
{
pq.pop();
}
}
for (int j = 0; j < appear[n - 1].size(); ++j)
{
pq.push(appear[n - 1][j]);
}
for (int i = 0; i < sizes.size(); ++i)
{
int pqsz = pq.size();
for (int j = 0; j < min(pqsz, time); ++j)
{
int tsz = pq.top();
if (tsz >= sizes[i]) break;
pq.pop();
}
}
if (pq.empty()) return true;
return false;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
sizes.resize(B);
for (int i = 0; i < B; ++i)
{
sizes[i] = Y[i];
}
appear.resize(A + 1);
sort(X, X + A); // weight limit of robots
sort(sizes.begin(), sizes.end()); // size limit of robots
for (int i = 0; i < T; ++i)
{
int idx = upper_bound(X, X + A, W[i]) - X;
int idx2 = upper_bound(sizes.begin(), sizes.end(), S[i]) - sizes.begin();
if (idx == A && idx2 == B) return -1;
appear[idx].push_back(S[i]);
}
reverse(sizes.begin(), sizes.end());
for (int i = 0; i < A + 1; ++i)
{
sort(appear[i].begin(), appear[i].end(), greater<int>());
}
int l = 1, r = T + 10;
while (l < r)
{
// cout << l << ' ' << r << endl;
int m = l + (r - l) / 2;
if (check(m))
{
r = m;
}
else
{
l = m + 1;
}
}
return l;
}
signed main()
{
init();
int A, B, T;
cin >> A >> B >> T;
int X[A], Y[B], W[T], S[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 >> W[i] >> S[i];
}
cout << putaway(A, B, T, X, Y, W, S) << endl;
return 0;
}