Submission #1152823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152823		at128	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	35 ms	4116 KiB

molecules

#include <vector>
#include <algorithm>
using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int, int>> sorted_w;
    for (int i = 0; i < w.size(); ++i) {
        sorted_w.emplace_back(w[i], i);
    }
    sort(sorted_w.begin(), sorted_w.end());

    // Check single elements
    for (auto &[weight, idx] : sorted_w) {
        if (weight >= l && weight <= u) {
            return {idx};
        }
    }

    // Sliding window
    int n = sorted_w.size();
    int left = 0;
    long long current_sum = 0;
    vector<int> result;

    for (int right = 0; right < n; ++right) {
        current_sum += sorted_w[right].first;
        while (current_sum > u && left <= right) {
            current_sum -= sorted_w[left].first;
            left++;
        }
        if (current_sum >= l) {
            for (int k = left; k <= right; ++k) {
                result.push_back(sorted_w[k].second);
            }
            sort(result.begin(), result.end());
            return result;
        }
    }

    return {};
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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