| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1336605 | iamhereforfun | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
#include "robots.h"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
int putaway(int n, int m, int q, vector<int> a, vector<int> b, vector<int> w, vector<int> s)
{
vector<pair<int, int>> query;
for (int &i : a)
i--;
for (int &i : b)
i--;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int x = 0; x < q; x++)
{
query.push_back({w[x], s[x]});
}
sort(query.begin(), query.end());
int l = 1, r = q, ans = -1;
// int l = 3, r = 3, ans = -1;
while (l <= r)
{
int md = (l + r) / 2;
int i = 0;
priority_queue<int> pq;
for (int x = 0; x < n; x++)
{
while (i < q)
{
if (query[i].first > a[x])
{
break;
}
else
{
pq.push(query[i].second);
i++;
}
}
for (int y = 0; y < md; y++)
{
if (!pq.empty())
pq.pop();
else
break;
}
}
while (i < q)
{
pq.push(query[i].second);
i++;
}
priority_queue<int> pq2;
while (!pq.empty())
{
pq2.push(-pq.top());
pq.pop();
}
for (int x = 0; x < m; x++)
{
for (int y = 0; y < md; y++)
{
if (pq2.empty())
break;
if (-pq2.top() <= b[x])
{
pq2.pop();
}
else
{
break;
}
}
}
if (pq2.empty())
{
ans = md;
r = md - 1;
}
else
{
l = md + 1;
}
}
return ans;
}