Submission #781192

#	Time	Username	Problem	Language	Result	Execution time	Memory
781192		sadsa	Detecting Molecules (IOI16_molecules)	C++17	10 / 100	1 ms	304 KiB

molecules

#include "molecules.h"

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

using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    ((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

std::vector<int> find_subset(int L, int U, std::vector<int> w) {
    const int N = w.size();

    vi sorted(N);
    iota(RANGE(sorted), 0);
    stable_sort(RANGE(sorted), [&] (auto a, auto b) {
        return w[a] < w[b];
    });

    DBG(sorted);

    vl sum(N+1);

    for (int i = 1; i <= N; ++i) {
        sum[i] = sum[i-1] + i64(w[sorted[i-1]]);
    }

    DBG(sum);

    for (int i = 1; i <= N; ++i) {
        int l, r;

        l = i;
        r = N;

        while (l < r) {
            int mid = (l+r+1) / 2;

            i64 rsum = sum[mid] - sum[i-1];

            if (rsum > U) {
                r = mid-1;
            } else if (rsum < L) {
                l = mid;
            } else {
                l = i;
                r = mid;
                DBG(l, r, rsum);
                vi ans;
                ans.reserve(r-l);
                for (i = l; i <= r; ++i) {
                    ans.push_back(sorted[i-1]);
                }
                DBG(ans);
                return ans;
            }
        }
    }

    return {};
}

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