Submission #942829

#	Time	Username	Problem	Language	Result	Execution time	Memory
942829		irmuun	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	40 ms	7256 KiB

molecules

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

vector<int>find_subset(int l,int u,vector<int>w){
    int n=(int)w.size();
    vector<pair<ll,int>>v(n);
    ll L=l,U=u,tot=0;
    for(int i=0;i<n;i++){
        v[i].ff=w[i];
        v[i].ss=i;
    }
    sort(all(v));
    int r=0;
    vector<int>ans;
    for(int i=0;i<n;i++){
        if(tot+v[i].ff<=U){
            tot+=v[i].ff;
            r=i+1;
            ans.pb(i);
        }
        else{
            break;
        }
    }
    if(r==0) return {};
    if(r==n&&tot<L) return {};
    if(L<=tot&&tot<=U){
        for(auto &x:ans){
            x=v[x].ss;
        }
        return ans;
    }
    ll curr=n-1;
    for(int i=(int)ans.size()-1;i>=0;i--){
        if(tot-v[ans[i]].ff+v[curr].ff<L){
            tot=tot-v[ans[i]].ff+v[curr].ff;
            ans[i]=curr;
            curr--;
        }
        else{
            for(int j=ans[i]+1;j<=curr;j++){
                tot=tot-v[ans[i]].ff+v[j].ff;
                ans[i]=j;
                if(L<=tot) break;
            }
            break;
        }
    }
    if(tot<L) return {};
    for(auto &x:ans){
        x=v[x].ss;
    }
    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