Submission #424543

#	Time	Username	Problem	Language	Result	Execution time	Memory
424543		benedict0724	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	96 ms	11280 KiB

molecules

#include "molecules.h"
#include <algorithm>
using namespace std;
typedef long long ll;
vector<int> find_subset(int l, int u, std::vector<int> w) {
    ll s = 1e15;
    int n = (int)w.size();
    for(int i=0;i<n;i++) s = min(s, (ll)w[i]);
    vector<ll> pre, suf;
    vector<pair<ll, ll>> v;
    for(int i=0;i<n;i++) pre.push_back(w[i] - s);
    for(int i=0;i<n;i++) suf.push_back(w[i] - s);
    for(int i=0;i<n;i++) v.push_back({w[i], i});
    sort(pre.begin(), pre.end());
    sort(suf.rbegin(), suf.rend());
    for(int i=1;i<n;i++) pre[i] += pre[i-1];
    for(int i=1;i<n;i++) suf[i] += suf[i-1];
    sort(v.begin(), v.end());
    vector<int> ans;
    for(int i=1;i<=n;i++)
    {
        ll m_in = s * i + pre[i-1], m_ax = s * i + suf[i-1];
        if(m_ax < l || u < m_in) continue;
        ll now = m_in;
        for(int j=0;j<=i;j++)
        {
            if(l <= now && now <= u)
            {
                for(int k=0;k<j;k++)
                {
                    ans.push_back(v[n-1-k].second);
                }
                for(int k=0;k<i-j;k++)
                {
                    ans.push_back(v[k].second);
                }
                return ans;
            }
            now -= pre[i-1-j];
            if(j < i-1) now += pre[i-2-j];
            if(j > 0) now -= suf[j-1];
            now += suf[j];
        }
    }
    return ans;
}

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