Submission #923591

#	Time	Username	Problem	Language	Result	Execution time	Memory
923591		velislavgarkov	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	43 ms	8788 KiB

molecules

#include "molecules.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=2e5+10;
pair <long long, int> a[MAXN];
long long pref[MAXN], n;
vector <int> find_subset(int lef, int u, vector <int> w) {
    n=w.size();
    pref[0]=0;
    for (int i=1;i<=n;i++) {
        a[i].first=w[i-1];
        a[i].second=i-1;
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++) pref[i]=a[i].first+pref[i-1];
    vector <int> ans;
    for (int i=1;i<=n;i++) {
        int l, r, mid;
        l=1; r=i;
        while (l<=r) {
            mid=(l+r)/2;
            if (pref[i]-pref[mid-1]<lef) r=mid-1;
            else l=mid+1;
        }
        if (r>0 && pref[i]-pref[r-1]<=u && pref[i]-pref[r-1]>=lef) {
            //cout << i << ' ' << r << ' ' << pref[i]-pref[r-1] << endl;
            for (int j=r;j<=i;j++) ans.push_back(a[j].second);
            return ans;
        }
    }
    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