Submission #551019

#	Time	Username	Problem	Language	Result	Execution time	Memory
551019		Sergio_2357	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	62 ms	10400 KiB

molecules

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

using namespace std;

#define ll long long

std::vector<int> find_subset(int l, int u, vector<int> w)
{
    ll sum = 0;
    vector<ll> a(w.size());
    for (int i = 0; i < w.size(); i++)
        a[i] = w[i];
    ll n = a.size();
    vector<ll> us(n, 0);
    vector<pair<ll, ll>> ri(n);
    for (int i = 0; i < n; i++)
        ri[i] = { w[i], i };
    sort(a.begin(), a.end());
    sort(ri.begin(), ri.end());
    ll s = 0;
    ll e = n - 1;
    while (sum < l && e >= 0) {
        us[e] = 1;
        sum += a[e];
        e--;
        //cout << sum << endl;
    }
    e = n - 1;
    while (sum > u && s < e) {
        if (!us[e] || us[s])
            break;
        us[e] = 0;
        us[s] = 1;
        sum -= a[e];
        sum += a[s];
        e--;
        s++;
        //cout << sum << endl;
    }
    if (sum >= l && sum <= u) {
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (us[i])
                res.push_back(ri[i].second);
        }
        sort(res.begin(), res.end());
        return res;
    } else {
        return vector<int>(0);
    }
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     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