Submission #843645

#	Time	Username	Problem	Language	Result	Execution time	Memory
843645		Mr_Husanboy	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	40 ms	4956 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
 
using namespace std;
 
template<typename T>
int len(T &a){return a.size();}

#define all(a) (a).begin(), (a).end()
 


vector<int> find_subset(int a, int b, vector<int> w) {
    int n = len(w);

    vector<int> p(n);
    iota(all(p), 0);
    sort(all(p), [&](int i, int j){
        return w[i] < w[j];
    });


    int l = 0, r = 0;
    long long cur = 0;
    queue<int> q;
    while(r < n){
        cur += w[p[r]];
        q.push(p[r]);
        while(l <= r && cur > b) cur -= w[p[l ++]], q.pop();
        if(cur >= a) break;
        r ++;
    }
    vector<int> ans;
    if(cur >= a){
        while(!q.empty()) ans.push_back(q.front()), q.pop();
    }
    return ans;
}

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