Submission #567895

#	Time	Username	Problem	Language	Result	Execution time	Memory
567895		ngpin04	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	36 ms	4148 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> solve(int cnt, int l, int r, vector <int> w, vector <int> ind) {
    int n = w.size();
    vector <int> used(n, 0);
    
    int tot = 0;
    for (int i = 0; i < cnt; i++) {
        used[i] = true;
        tot += w[ind[i]];
        // cerr << ind[i] << " ";
    }

    for (int i = cnt - 1, las = n; i >= 0; i--) {
        if (tot >= l)
            break;
        int lo = i;
        int hi = las;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            int dif = w[ind[mid]] - w[ind[i]];
            if (tot + dif <= r)
                lo = mid;
            else
                hi = mid;
        }
        int dif = w[ind[lo]] - w[ind[i]];

        las = lo;
        tot += dif;
        used[i] = false;
        used[lo] = true;
    }

    vector <int> res;
    for (int i = 0; i < n; i++)
        if (used[i])
            res.push_back(ind[i]);
    return res;
}

vector<int> find_subset(int l, int u, vector<int> w) {
    if (accumulate(ALL(w), 0LL) < l || *min_element(ALL(w)) > u) 
        return vector <int> (0);
    int n = w.size();
    vector <int> ind(n, 0);
    iota(ALL(ind), 0);
    sort(ALL(ind), [&](int i, int j) {
        return w[i] < w[j];
    });

    for (int cnt = 1, pre = 0, suf = 0; cnt <= n; cnt++) {
        pre += w[ind[cnt - 1]];
        suf += w[ind[n - cnt]];
        if (pre > u)
            break;
        if (suf < l)
            continue;
        // cerr << cnt << " " << pre << " " << suf << "\n";
        return solve(cnt, l, u, w, ind);
    }

    return vector <int> (0);
}

//#include "grader.cpp"

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