Submission #63624

#	Time	Username	Problem	Language	Result	Execution time	Memory
63624		MKopchev	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	87 ms	10900 KiB

molecules

/*
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
pair<int,int> arr[nmax];
long long sums[nmax];
int find_subset(int l, int u, int w[], int n, int result[])
{
    for(int i=0;i<n;i++)
        arr[i+1]={w[i],i};
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n;i++)
        sums[i]=sums[i-1]+arr[i].first;
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(sums+1,sums+n+1,sums[i-1]+l)-sums;
        if(p>n)continue;
        if(sums[p]-sums[i-1]>u)continue;
        for(int j=i;j<=p;j++)
            result[j-i]=arr[j].second;
        //for(int j=i;j<=p;j++)cout<<arr[j].second<<" ";cout<<endl;
        //for(int j=0;j<=p-i;j++)cout<<result[j]<<" ";cout<<endl;
        return p-(i-1);
    }
    return 0;
}
*/
#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
pair<int,int> arr[nmax];
long long sums[nmax];
vector<int> find_subset(int l, int u, vector<int> w)
{
    int n=w.size();
    for(int i=0;i<n;i++)
        arr[i+1]={w[i],i};
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n;i++)
        sums[i]=sums[i-1]+arr[i].first;
    vector<int> result={};
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(sums+1,sums+n+1,sums[i-1]+l)-sums;
        if(p>n)continue;
        if(sums[p]-sums[i-1]>u)continue;
        for(int j=i;j<=p;j++)
            result.push_back(arr[j].second);
        //for(int j=i;j<=p;j++)cout<<arr[j].second<<" ";cout<<endl;
        //for(int j=0;j<=p-i;j++)cout<<result[j]<<" ";cout<<endl;
        return result;
    }
    return result;
}

/*
int l=15,u=17;
//int l=14,u=15;
int w[4]={6,8,8,7};
//int w[4]={5,5,6,6};
int n=4;
int result[4];
int main()
{
find_subset(l,u, w, n, result);
}
*/

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