Submission #678896

#	Time	Username	Problem	Language	Result	Execution time	Memory
678896		Genius3435	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	48 ms	5580 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;

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

    deque<pair<u32, int>> w, used;
    for (int i = 0; i < n; ++i) {
        w.emplace_back(_w[i], i);
    }
    sort(w.begin(), w.end());

    u32 s = 0;
    while (s < l && !w.empty()) {
        auto const [x, i] = w.front();
        if (s+x > u) break;
        w.pop_front();
        used.emplace_back(x, i);
        s += x;
    }

    while (s < l && !w.empty()) {
        auto const [x, i] = used.front();
        auto const [y, j] = w.back();
        s -= x, s += y;
        used.pop_front();
        w.pop_back();
        used.emplace_back(y, j);
    }

    if (l <= s && s <= u) {
        vector<int> ans; ans.reserve(used.size());
        for (auto const &[x, i] : used) ans.push_back(i);
        return ans;
    }

    else {
        return vector<int>();
    }
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:14: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   15 |     while (s < l && !w.empty()) {
      |            ~~^~~
molecules.cpp:17:17: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   17 |         if (s+x > u) break;
      |             ~~~~^~~
molecules.cpp:23:14: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   23 |     while (s < l && !w.empty()) {
      |            ~~^~~
molecules.cpp:32:11: warning: comparison of integer expressions of different signedness: 'int' and 'u32' {aka 'unsigned int'} [-Wsign-compare]
   32 |     if (l <= s && s <= u) {
      |         ~~^~~~
molecules.cpp:32:21: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   32 |     if (l <= s && s <= u) {
      |                   ~~^~~~

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