| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 545076 | LunaMeme | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
struct weight{
int val, i;
weight(int val, int i) : val(val), i(i) {}
bool operator<(const weight& rhs){
return val < rhs.val;
}
};
struct CompareWeight{
bool operator()(const weight& lhs, const weight& rhs){
return lhs.val < rhs.val;
}
};
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
vector<weight> v;
FOR(i, 0, (int)w.size()){
v.PB(weight(w[i], i));
}
sort(v.begin(), v.end());
vi sol;
ll sum = 0;
priority_queue<weight, vector<weight>, CompareWeight> p;
if (v[0].val > u)
return sol;
FOR(i, 0, (int)w.size()){
if (sum + v[i].val < l){
sum += v[i].val;
p.push(v[i]);
}
else if (sum +v[i].val <= u){
p.push(v[i]);
break;
}
else {
weight mn = p.top();
p.pop();
sum += v[i].val - mn.val;
if (sum >= l){
break;
}
}
if (i == (int)w.size() - 1){
return std::vector<int>(0);
}
}
while(!p.empty()){
weight a = p.top(); p.pop();
sol.PB(a.i);
}
return sol;
}
int main() {
int n, l, u;
assert(3 == scanf("%d %d %d", &n, &l, &u));
std::vector<int> w(n);
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &w[i]));
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%c", result[i], " \n"[i == (int)result.size() - 1]);
}