| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 988557 | Wane | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <queue>
#include <stack>
#include "molecules.h"
#define int long long
#define pp std::pair<int, int>
bool cmp1(pp a, pp b) {
return a.first > b.first;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
std::vector<pp> wp;
for (int i = 0; i < w.size(); i++) wp.push_back({w[i], i});
// Notice that w_max - w_min is always smaller than u - l.
sort(wp.begin(), wp.end(), cmp1);
// We can just put ALL things down here first, and 'replace' them until it satisfies the condition;
std::priority_queue<pp> q;
std::priority_queue<pp> d;
//cout << l << ' ' << u << '\n';
int man = 0;
for (auto a : wp) {
if (man > l) {
//cout << a.first << " << D, ";
d.push(a); // it means 'ready' queue
continue;
}
//cout << a.first << " << Q, ";
q.push(a); man += a.first;
}
//cout << "Man: " << man << '\n';
if (man < l) {
return {}; // Impossible!
}
while (!d.empty() && man > u) {
// Replace d's top and q's top, but there's no more usage for q's top so just fuck it off
auto dt = d.top();
auto qt = q.top();
q.pop(); d.pop();
q.push(dt);
man -= qt.first - dt.first;
}
if (man > u) {
return {};
}
std::vector<int> ans;
while (!q.empty()) {
ans.push_back(q.top().second);
//cout << q.top().second << ' ';
q.pop();
}
//cout << '\n';
return ans;
}
/*
signed main() {
int n, l, u;
cin >> n >> l >> u;
std::vector<int> w(n);
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &w[i]));
//cout << l << ' ' << u << '\n';
std::vector<int> result = find_subset(l, u, w);
printf("%d\n", (int)result.size());
for (int i = 0; i < (int)result.size(); i++)
printf("%d ", result[i]);
}
*/