Submission #1301164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301164		Math4Life2020	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	37 ms	8332 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

vector<int> find_subset(int _l, int _u, vector<int> _w) {
    ll N = _w.size();
    ll l = _l; ll u = _u;
    //sort(w.begin(),w.end());
    vector<pii> pw;
    for (ll x=0;x<N;x++) {
        pw.push_back({_w[x],x});
    }
    sort(pw.begin(),pw.end());
    ll w[N];
    for (ll i=0;i<N;i++) {
        w[i]=pw[i].first;
    }
    vector<int> vf;
    ll pfs[N+1];
    pfs[0]=0;
    for (ll t=0;t<N;t++) {
        pfs[t+1]=pfs[t]+w[t];
    }
    for (ll T=1;T<=N;T++) {
        ll smin = pfs[T];
        ll smax = pfs[N]-pfs[N-T];
        //cout << "T="<<T<<", smin="<<smin<<", smax="<<smax<<"\n";
        if (smax<l || u<smin) {
            continue;
        }
        //cout << "f1\n";
        for (ll xl=0;xl<T;xl++) {
            ll bs0 = pfs[xl]+pfs[N]-pfs[N-T+xl+1];
            //0, 1, 2, ..., xl-1
            //and
            //N-(T-xl-1), N-(T-xl-2), ..., N-2, N-1
            ll vmin = bs0 + w[xl];
            ll vmax = bs0 + w[N-T+xl];
            //cout << "xl="<<xl<<", vmin="<<vmin<<", vmax="<<vmax<<"\n";
            if (vmax<l || u<vmin) {
                continue;
            }
            //cout << "f2\n";
            vector<int> vans;
            for (ll t=0;t<xl;t++) {
                vans.push_back(pw[t].second);
            }
            for (ll t=(N-T+xl+1);t<N;t++) {
                vans.push_back(pw[t].second);
            }
            for (ll t=xl;t<=(N-T+xl);t++) {
                if (l<=(bs0+w[t])&&(bs0+w[t])<=u) {
                    vans.push_back(pw[t].second);
                    return vans;
                }
            }
        }
    }
    return vf;
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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