Submission #151546

#	Time	Username	Problem	Language	Result	Execution time	Memory
151546		mhy908	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	70 ms	6424 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long LL;

int N;
int A[MAXN];
LL S[MAXN];

vector<int> find_subset(int l, int u, vector<int> w)
{
    int t = 0;
    N = sz(w);
    for (int i=1;i<=N;i++) A[i] = i;
    sort(A+1, A+N+1, [&w](const int &a, const int &b){
        return w[a-1] < w[b-1];
    });
    for (int i=1;i<=N;i++)
        S[i] = S[i-1] + w[A[i]-1];
    for (int i=1;i<=N;i++){
        LL p = S[i];
        LL q = S[N]-S[N-i];
        if (p <= u && q >= l){ t = i; break; }
    }
    vector <int> ret;
    if (!t) return ret;
    for (int i=t;i<=N;i++){
        LL v = S[i] - S[i-t];
        if (v < l || v > u) continue;
        for (int j=0;j<t;j++) ret.pb(A[i-j]-1);
        break;
    }
    return ret;
}

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