Submission #1301158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301158		Math4Life2020	Detecting Molecules (IOI16_molecules)	C++20	9 / 100	1 ms	352 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) {
    sort(w.begin(),w.end());
    vector<int> vf;
    ll N = w.size();
    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];
        if (smax<l || u<smin) {
            continue;
        }
        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];
            if (vmax<l || u<vmin) {
                continue;
            }
            vector<int> vans;
            for (ll t=0;t<xl;t++) {
                vans.push_back(t);
            }
            for (ll t=(N-T+xl+1);t<N;t++) {
                vans.push_back(t);
            }
            for (ll t=xl;t<=(N-T+xl);t++) {
                if (l<=(bs0+w[t])&&(bs0+w[t])<=u) {
                    vans.push_back(t);
                    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: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31