Submission #1291465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291465		hssaan_arif	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	79 ms	12928 KiB

molecules

#include <vector>
#include <set>
#include <algorithm>
#include "molecules.h"

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int, int>> v;
    for (int i = 0; i < w.size(); i++) v.push_back({w[i], i});
    
    sort(v.rbegin(), v.rend());
    
    long long sum = 0;
    int last = w.size() - 1;
    set<int> ans;
    
    for (int i = 0; i < v.size(); i++) {
        sum += v[i].first;
        ans.insert(v[i].second);
        
        if (sum >= l && sum <= u) 
            return vector<int>(ans.begin(), ans.end());
        
        if (sum > u) {
            int attempts = i + 1;
            while (attempts--) {
                sum -= v[i].first;
                ans.erase(v[i].second);
                sum += v[last].first;
                ans.insert(v[last].second);
                i--;
                last--;
                
                if (sum >= l && sum <= u) 
                    return vector<int>(ans.begin(), ans.end());
            }
            return vector<int>();
        }
    }
    return vector<int>();
}

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