Submission #415953

#	Time	Username	Problem	Language	Result	Execution time	Memory
415953		TLP39	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	304 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
ll 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)];
        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];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        qs_f+=(ll)a[i];
        qs_b+=(ll)a[n-1-i];
        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)]);
        hi-=min(n-num,hi);
    }
    return res;
}

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