Submission #31089

#	Time	Username	Problem	Language	Result	Execution time	Memory
31089		TAMREF	Detecting Molecules (IOI16_molecules)	C++11	9 / 100	0 ms	2024 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<int> find_subset(int l, int u, std::vector<int> w) {
    int n=w.size();
    vector<pii> p(n);
    vector<int> ans;
    for(int i=0;i<n;i++) p[i]={w[i],i};
    sort(p.begin(),p.end());
    long long psum=0;
    if(p[0].first>=l && p[0].first<=u) return vector<int>(1,p[0].second);
    for(int i=0;i<n-1;i++){
        psum+=p[i].first;
        if(psum<=l && psum+p[n-1].first>=l+p[0].first){
            for(int j=1;j<=i;j++) ans.push_back(p[j].second);
            ans.push_back(p[n-1].second);
            return ans;
        }
    }
    psum+=p[n-1].first;
    if(psum>=l && psum<=u){
        for(pii &t : p) ans.push_back(t.second);
        return ans;
    }
    return vector<int>(0);
}

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