Submission #491941

#	Time	Username	Problem	Language	Result	Execution time	Memory
491941		TheScrasse	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	69 ms	11932 KiB

molecules

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 200010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b;
ll l, u, ps[maxn], p[maxn], bsl, bsm, bsu;
vector<int> rs;
vector<array<ll, 2>> v;

ll rsq(ll l, ll r) {
    if (l <= 0) return -INF;
    if (r >= n + 1) return INF;
    return (ps[r] - ps[l - 1]);
}

vector<int> find_subset(int _l, int _u, vector<int> w) {
    n = w.size(); l = _l; u = _u;

    for (i = 1; i <= n; i++) v.pb({w[i - 1], i});
    sort(v.begin(), v.end());

    for (i = 1; i <= n; i++) {
        a[i] = v[i - 1][0]; p[i] = v[i - 1][1];
    }

    for (i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];

    for (i = 1; i <= n; i++) {
        bsl = 0; bsu = n;
        while (bsl != bsu) {
            bsm = (bsl + bsu) / 2;
            if (rsq(bsm, bsm + i - 1) >= l) bsu = bsm;
            else bsl = bsm + 1;
        }

        k = rsq(bsl, bsl + i - 1);
        if (k < l || k > u) continue;
        for (j = bsl; j <= bsl + i - 1; j++) rs.pb(p[j] - 1);
        return rs;
    }

    return rs;
}

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