| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 985051 | normankr07 | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define taskname ""
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifndef LOCAL
#define cerr \
if (0) \
cerr
#endif
const bool multitest = 0;
int n, l, u;
vector<int> w;
std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
for (int i = 1; i <= w.size(); i++)
{
if (l <= w[i - 1] && w[i - 1] <= u)
{
return vector<int>(i);
}
}
vector<pair<int, int>> ww;
for (int i = 1; i <= n; i++)
{
ww.push_back(make_pair(w[i - 1], i));
}
sort(ww.begin(), ww.end());
ll sum = 0;
while (ww.size() && ww.back().first > l)
{
ww.pop_back();
}
vector<int> idans;
while (sum < l)
{
if (sum > u)
break;
sum += ww.back().first;
idans.push_back(ww.back().second);
ww.pop_back();
}
if (sum >= l && sum <= u)
{
sort(idans.begin(), idans.end());
return idans;
}
while (sum > u)
{
sum -= w[idans.back() - 1];
idans.pop_back();
}
int i = 0;
while (sum < l)
{
sum += ww[i].first;
idans.push_back(ww[i].second);
i++;
}
if (sum < l || sum > u)
return vector<int>();
sort(idans.begin(), idans.end());
return idans;
}
void solve()
{
cin >> n >> l >> u;
w.assign(n, 0);
for (auto &v : w)
cin >> v;
auto ans = find_subset(l, u, w);
for (auto v : ans)
{
cout << v << ' ';
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(taskname ".inp", "r"))
{
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out", "w", stdout);
}
int tc = 1;
if (multitest)
cin >> tc;
while (tc--)
{
solve();
cout << '\n';
}
}