Submission #741855

#	Time	Username	Problem	Language	Result	Execution time	Memory
741855		haydendoo	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	46 ms	7132 KiB

molecules

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

#define ll long long

vector<int> find_subset(int L, int U, vector<int> W) {
    ll l=L,u=U,n=W.size();
    pair<ll,ll> w[n];
    for(int i=0; i<n; ++i) w[i]={W[i],i};
    sort(w,w+n);
    ll left=0,curr=0;
    for(int i=0; i<n; ++i) {
        curr+=w[i].first;
        if(curr<l) continue;
        while(left<i && curr>u) {
            curr-=w[left].first; ++left;
        }
        if(curr>=l && curr<=u) {
            vector<int> ans;
            for(int j=left; j<=i; ++j) ans.push_back(w[j].second);
            return ans;
        }
    }
    return {};
}

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