Submission #1367670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367670		mariza	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	28 ms	6172 KiB

molecules

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

typedef long long ll;

vector<int> find_subset(int l, int r, vector<int> w) {
    ll n=w.size();
    vector<pair<ll,int>> a;
    for(ll i=0; i<n; i++){
        a.push_back({w[i],i});
    }
    sort(a.begin(),a.end());

    ll cl=l, cr=r;
    ll k=-1;
    for(ll i=0; i<n; i++){
        cl-=a[n-1-i].first;
        cr-=a[i].first;

        if(cl<=0 && 0<=cr) k=i+1;
    }

    if(k==-1) return vector<int>();
    else{
        ll x=0;
        for(ll i=0; i<k; i++){
            x+=a[n-1-i].first;
        }

        ll y=0;
        while(x>r){
            x-=a[n-k+y].first;
            x+=a[y].first;
            y++;
        }

        vector<int> ans;
        for(ll i=0; i<y; i++){
            ans.push_back(a[i].second);
        }
        for(ll i=0; i<k-y; i++){
            ans.push_back(a[n-1-i].second);
        }
        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