Submission #812768

#	Time	Username	Problem	Language	Result	Execution time	Memory
812768		jlallas384	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	41 ms	6824 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<int> find_subset(int l, int u, std::vector<int> w){
    vector<pair<int,int>> a;
    for(int i = 0; i < w.size(); i++){
        a.emplace_back(w[i], i);
    }
    sort(a.begin(), a.end());
    while(a.size() && a.back().first > u) a.pop_back();
    ll sum = 0;

    vector<int> ans;
    vector<ll> pre;
    pre.push_back(0);
    for(auto [v, i]: a){
        pre.push_back(pre.back() + v);
    }
    reverse(a.begin(), a.end());
    for(int i = 0; i <= a.size(); i++){
        int j = a.size() - 1;
        auto it = lower_bound(pre.begin(), pre.end(), max(0LL, l - sum));
        if(it != pre.end() && sum + *it <= u && sum + *it >= l && i <= a.size() - (it - pre.begin())){
            int idx = it - pre.begin();
            for(int j = 0; j < idx; j++){
                ans.push_back(a[a.size() - 1 - j].second);
            }
            return ans;
        }
        if(i < a.size() && sum + a[i].first <= u){
            ans.push_back(a[i].second);
            sum += a[i].first;
        }
    }
    return {};
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:6:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for(int i = 0; i < w.size(); i++){
      |                    ~~^~~~~~~~~~
molecules.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0; i <= a.size(); i++){
      |                    ~~^~~~~~~~~~~
molecules.cpp:23:69: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   23 |         if(it != pre.end() && sum + *it <= u && sum + *it >= l && i <= a.size() - (it - pre.begin())){
      |                                                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
molecules.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if(i < a.size() && sum + a[i].first <= u){
      |            ~~^~~~~~~~~~
molecules.cpp:21:13: warning: unused variable 'j' [-Wunused-variable]
   21 |         int j = a.size() - 1;
      |             ^

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