Submission #1070052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070052		TheQuantiX	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	33 ms	4048 KiB

molecules

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using ll = int;

ll n, m, q, k, x, y, a, b, c;

vector<int> gen(ll x, vector< pair<ll, ll> > &v, ll l, ll u) {
    vector<int> st;
    vector<int> ans;
    ll num = 0;
    ll e = n - 1;
    for (int i = x - 1; i >= 0; i--) {
        st.push_back(i);
        num += v[i].first;
    }
    while (num < l) {
        ll x = st[st.size() - 1];
        if (num - v[x].first + v[e].first <= u) {
            num -= v[x].first;
            num += v[e].first;
            ans.push_back(v[e].second);
            st.pop_back();
            e--;
        }
        else {
            num -= v[x].first;
            num += v[x + 1].first;
            st[st.size() - 1]++;
        }
    }
    for (auto i : st) {
        ans.push_back(v[i].second);
    }
    return ans;
}

vector<int> find_subset(int l, int u, vector<int> w) {
    n = w.size();
    vector<int> ans;
    vector< pair<ll, ll> > v;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        if (w[i] >= l && w[i] <= u) {
            ans.push_back(i);
            return ans;
        }
        v.push_back({w[i], i});
        sum += w[i];
    }
    sort(v.begin(), v.end());
    ll mn = 0, mx = 0;
    for (int i = 0; i < n; i++) {
        mn += v[i].first;
        mx += v[n - 1 - i].first;
        // cout << mn << ' ' << mx << '\n';
        if (min(mx, (ll)u) >= max(mn, (ll)l)) {
            return gen(i + 1, v, l, u);
        }
    }
    return ans;
}

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