Submission #415956

#	Time	Username	Problem	Language	Result	Execution time	Memory
415956		TLP39	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	59 ms	7108 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
pair<ll,int> a[200010];
ll qs_f=0,qs_b=0;
ll num=0;
ll hi,low,av;
ll L,U;

bool notlow(ll x)
{
    ll temp=x;
    ll sum=0;
    for(int i=num-1;i>=0;i--)
    {
        sum+=a[i+min(n-num,temp)].first;
        temp-=min(n-num,temp);
    }
    if(sum>=L) return true;
    return false;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    vector<int> res;
    n=w.size();
    L=(ll)l;
    U=(ll)u;
    for(int i=0;i<n;i++)
    {
        a[i]={(ll)w[i],i};
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        qs_f+=a[i].first;
        qs_b+=a[n-1-i].first;
        if(qs_f<=U && qs_b>=L)
        {
            num=(ll)(i+1);
            break;
        }
    }

    if(!num) return res;
    low=0;
    hi=((ll)n-num)*num;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(notlow(av)) hi=av;
        else low=av+1;
    }
    for(int i=num-1;i>=0;i--)
    {
        res.push_back(a[i+min(n-num,hi)].second);
        hi-=min(n-num,hi);
    }
    return res;
}

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