제출 #1360054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360054		skuru	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	23 ms	5276 KiB

molecules

#include "molecules.h"
#include <algorithm>
using namespace std;

using ll = long long;

#define all(v) (v).begin(), (v).end()
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }

struct Molecule {
    ll w;
    int idx;
};

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();

    vector<Molecule> molecules(n);
    for (int i = 0; i < n; i++)
        molecules[i] = {w[i], i};

    sort(all(molecules), by(w));

    ll sum = 0;
    int hi = 0;
    while (hi < n and sum < l)
        sum += molecules[hi++].w;
    hi--;

    if (sum < l)
        return {};

    if (sum <= u) {
        vector<int> ret;
        for (int i = 0; i <= hi; i++)
            ret.push_back(molecules[i].idx);
        return ret;
    }

    sum -= molecules[0].w;
    int lo = 1;
    while (hi + 1 < n and sum < l)
        sum += molecules[++hi].w - molecules[lo++].w;

    if (l <= sum) {
        vector<int> ret;
        for (int i = lo; i <= hi; i++)
            ret.push_back(molecules[i].idx);
        return ret;
    }

    return {};
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 10 / 10
• 서브태스크 3: 12 / 12
• 서브태스크 4: 15 / 15
• 서브태스크 5: 23 / 23
• 서브태스크 6: 31 / 31