Submission #990835

#	Time	Username	Problem	Language	Result	Execution time	Memory
990835		phoenix	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	34 ms	2908 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;


vector<int> find_subset(int L, int R, vector<int> w) {
    int n = (int)w.size();
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return (w[a] < w[b]);
    });

    int l = 0;
    ll sum = 0;
    for (int r = 0; r < n; r++) {
        sum += w[ord[r]];
        while (sum > R) {
            sum -= w[ord[l++]];
        }
        if (L <= sum) {
            vector<int> res;
            for (int i = l; i <= r; i++) 
                res.push_back(ord[i]);
            return res;
        }
    }

    return vector<int>(0);
}

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