Submission #781169

#	Time	Username	Problem	Language	Result	Execution time	Memory
781169		sadsa	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	1085 ms	6804 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 l = 1; l <= N; ++l) {
        for (int r = l; r <= N; ++r) {
            auto rsum = sum[r] - sum[l-1];
            if (rsum >= L && rsum <= U) {
                DBG(l, r, rsum);
                vi ans;
                ans.reserve(r-l);
                for (int i = l; i <= r; ++i) {
                    ans.push_back(sorted[i-1]);
                }
                DBG(ans);
                return ans;
            }
        }
    }

    return {};
}

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