Submission #369682

#	Time	Username	Problem	Language	Result	Execution time	Memory
369682		KoD	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	65 ms	4588 KiB

molecules

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

template <class T>
using Vec = std::vector<T>; 

Vec<int> find_subset(int l, int u, Vec<int> w) {
    const int n = (int) w.size();
    Vec<std::pair<int, int>> vec;
    vec.reserve(n);
    for (int i = 0; i < n; ++i) {
        vec.emplace_back(w[i], i);
    }
    std::sort(vec.begin(), vec.end());
    long long lsum = 0, rsum = 0;
    for (int k = 1; k <= n; ++k) {
        lsum += vec[k - 1].first;
        rsum += vec[n - k].first;
        if (lsum <= u && l <= rsum) {
            int last = k;
            long long cur = lsum;
            while (true) {
                if (l <= cur && cur <= u) {
                    Vec<int> ret;
                    for (int i = last - k; i < last; ++i) {
                        ret.push_back(vec[i].second);
                    }
                    return ret;
                }
                if (last == n) {
                    break;
                }
                cur -= vec[last - k].first;
                cur += vec[last].first;
                last += 1;
            }
        }
    }
    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