Submission #571119

#	Time	Username	Problem	Language	Result	Execution time	Memory
571119		stevancv	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	52 ms	5812 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e9;
int mod = 1000000007;
vector<int> find_subset(int L, int R, vector<int> W) {
    int n = W.size();
    ll l = L;
    ll r = R;
    vector<ll> w(n);
    for (int i = 0; i < n; i++) w[i] = W[i];
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&] (int i, int j) {
            return w[i] < w[j];
    });
    ll sum = 0;
    int kolko = 0;
    for (int i : order) {
        if (sum + w[i] <= r) {
            sum += w[i];
            kolko++;
        }
    }
    vector<int> ans;
    for (int i = 0; i < kolko; i++) {
        ans.push_back(order[i]);
    }
    if (sum >= l) return ans;
    ll fali = l - sum;
    int lo = 0, hi = n - 1;
    while (lo < kolko && kolko <= hi) {
        ll delta = w[order[hi]] - w[order[lo]];
        fali -= delta;
        ans[lo] = order[hi];
        if (fali <= 0) break;
      	lo += 1;
      	hi -= 1;
    }
    sum = 0;
    for (int i = 0; i < kolko; i++) sum += w[ans[i]];
    if (sum < l) return {};
    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