Submission #715662

#	Time	Username	Problem	Language	Result	Execution time	Memory
715662		ovidiush11	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	1 ms	212 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

#define ll long long

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
    ll n = w.size();
    vector<pair<ll,ll>> a(n);
    for(ll i = 0;i < n;i++)a[i] = {w[i],i};
    sort(a.begin(),a.end());
    ll N = n,s = 0;
    while(N != 0 && s + w[N-1] < l){s += a[N-1].first;N--;}
    if(N == n)
    {
        for(int i = 0;i < n;i++)if(w[i] >= l && w[i] <= u)return {i};
        return {};
    }
    if(N == 0)return {};
    N = n - N;s = 0;
    vector<pair<ll,ll>> p(n-N);
    for(ll i = N;i < n;i++)p[i-N] = a[i];
    for(ll i = 0;i < N-1;i++)s += a[i].first;
    ll k = 0;
    for(ll i = N-1;i < n;i++)
    {
        s += a[i].first;
        ll left = 0,right = n-N-1;
        while(left != right)
        {
            ll mid = (left + right) / 2;
            if(p[mid].first + s < l)left++;
            else if(p[mid].first + s > u)right--;
            else left = right = mid;
        }
        if(p[left].first + s >= l && p[left].first + s <= u)
        {
            vector<int> ans;
            for(ll j = i;j >= k;j--)ans.push_back(a[j].second);
            ans.push_back(p[left].second);
            return ans;
        }
        s -= a[k].first;
        if(k < n-N)p[k] = a[k];
        k++;
    }
    return {};
}

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