Submission #558734

#	Time	Username	Problem	Language	Result	Execution time	Memory
558734		elazarkoren	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	46 ms	4792 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

vi find_subset(int l, int u, vi w) {
    int n = w.size();
    vi ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&] (int i, int j) {
        return w[i] < w[j];
    });
    ll s = 0;
    for (int x : w) s += x;
    int k = n;
    for (; s > u; s -= w[ind[--k]]);
    if (!k) return {};
    if (s >= l) {
        vi v(k);
        for (int i = 0; i < k; i++) v[i] = ind[i];
        return v;
    }
    int left = k - 1, right = n - 1;
    while (s < l) {
        if (left < 0) return {};
        s -= w[ind[left]];
        left--;
        if (s + w[ind[right]] < l) {
            s += w[ind[right--]];
            continue;
        }
        int begin = left, end = right, mid;
        while (begin < end) {
            mid = (begin + end) >> 1;
            if (s + w[ind[mid]] < l) {
                begin = mid + 1;
            } else end = mid;
        }
        if (l <= s + w[ind[end]] && s + w[ind[end]] <= u) {
            vi v;
            for (int i = 0; i <= left; i++) v.push_back(ind[i]);
            v.push_back(ind[end]);
            for (int i = right + 1; i < n; i++) v.push_back(ind[i]);
            return v;
        }
        break;
    }
    return {};
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31