Submission #591394

#	Time	Username	Problem	Language	Result	Execution time	Memory
591394		yutabi	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	71 ms	6300 KiB

molecules

#include "molecules.h"


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


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;


std::vector<int> find_subset(int l, int u, std::vector<int> s)
{
    int n=s.size();

    vector <ii> w;

    for(int i=0;i<n;i++)
    {
        w.pb(ii(s[i],i));
    }

    set <int> ans;

    ll L=0;
    ll R=0;

    sort(w.begin(),w.end());

    int ans_size=-1;

    for(int i=0;i<n;i++)
    {
        L+=w[i].first;
        R+=w[n-i-1].first;

        if(L<=u && l<=R)
        {
            ans_size=i+1;
        }

        //printf("%lld %lld %d %d\n",L,R,l,u);
    }

    if(ans_size==-1)
    {
        return std::vector<int>(0);
    }

    ll sum=0;

    for(int i=0;i<ans_size;i++)
    {
        ans.insert(w[i].second);
        sum+=w[i].first;
    }

    for(int i=ans_size;i<n;i++)
    {
        if(l<=sum && sum<=u)
        {
            break;
        }

        ans.erase(w[i-ans_size].second);

        sum-=w[i-ans_size].first;

        ans.insert(w[n-(i-ans_size)-1].second);
        sum+=w[n-(i-ans_size)-1].first;
    }

    vector <int> fnl;

    for(set <int>::iterator it=ans.begin();it!=ans.end();it++)
    {
        fnl.pb(*it);
    }

    return fnl;
}

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