Submission #1010204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010204		Unlucky	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	6356 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> find_subset(int l, int u, vector<int> w1) {
    vector<pair<int, int>> w(w1.size());
    for (int i = 0; i < w.size(); i++){
        w[i] = {w1[i], i};
    }
    sort(w.begin(), w.end());
    long long s = 0;
    priority_queue<pair<int, int>> added;
    int i = w.size()-1;
    while (i >= 0 && s < l){
        s += w[i].first;
        added.push(w[i]);
        i--;
    }
    if (s < l){
        return vector<int>(0);
    }
    while (i >= 0 && s > u){
        s -= added.top().first;
        added.pop();
        s += w[i].first;
        added.push(w[i]);
        i--;
    }
    if (s <= u && s >= l){
        int n = added.size();
        vector<int> ret(n);
        for (int i = 0; i < n; i++){
            ret[i] = added.top().second;
            added.pop();
        }
        sort(ret.begin(), ret.end());
        return ret;
    }
    return vector<int>(0);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < w.size(); i++){
      |                     ~~^~~~~~~~~~

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