Submission #575891

#	Time	Username	Problem	Language	Result	Execution time	Memory
575891		jasmin	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	5552 KiB

molecules

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

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

    int l=0; int r=0;
    long long sum=a[0].first;
    while(l<=r && r<n){
        if(left<=sum && sum<=right){
            vector<int> ans;
            for(int i=l; i<=r; i++){
                ans.push_back(a[i].second);
            }
            return ans;
        }

        if(right<sum){
            sum-=a[l].first;
            l++;
        }
        else{
            r++;
            sum+=a[r].first;
        }
    }
    return {};
}

/*signed main(){
    int n;
    cin >> n;
    int l, r;
    cin >> l >> r;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    vector<int> ans=find_subset(l, r, a);
    for(auto e: ans){
        cout << e << " ";
    }
    cout << "\n";
}*/

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