Submission #853190

#	Time	Username	Problem	Language	Result	Execution time	Memory
853190		hngwlog	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	420 KiB

molecules

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

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

vector<int> find_subset(int l, int u, vector<int> w) {

    vector<pair<int, int>> g;
    int n = _size(w);
    REP(i, n) g.push_back({w[i], i});
    sort(g.begin(), g.end());
    priority_queue<pair<int, int>> inPQ, notinPQ;
    int res = 0;
    REP(i, n) {
        if (res + g[i].fi <= l) {
            res += g[i].fi;
            inPQ.push({- g[i].fi, g[i].se});
        }
        else notinPQ.push(g[i]);
    }
    if (res < l && notinPQ.empty()) return {};
    if (inPQ.empty()) {
        if (res + g[0].fi <= u) return {g[0].se};
        else return {};
    }
    while (res < l) {
        pair<int, int> subtract = inPQ.top();
        inPQ.pop();
        pair<int, int> add = notinPQ.top();
        notinPQ.pop();
        if (add.fi + subtract.fi <= 0) return {};
        res += (add.fi + subtract.fi);
        inPQ.push({- add.fi, add.se});
        notinPQ.push({- subtract.fi, subtract.se});
    }
    vector<pair<int, int>> _g;
    while (!notinPQ.empty()) {
        _g.push_back(notinPQ.top());
        notinPQ.pop();
    }
    vector<int> ans;
    while (!inPQ.empty()) {
        ans.push_back(inPQ.top().se);
        inPQ.pop();
    }
    if (res < l) {
        if (_size(_g) && res + _g.back().fi >= l &&  res + _g.back().fi <= u) ans.push_back(_g.back().se);
        else return {};
    }
    sort(ans.begin(), ans.end());
    return ans;
}

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