Submission #854552

#	Time	Username	Problem	Language	Result	Execution time	Memory
854552		fanwen	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	600 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#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 FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

vector <int> find_subset(int L, int R, vector <int> w) {
    int n = (int) w.size();
    vector <pair <int, int>> a;
    vector <int> ans;
    for (int i = 0; i < n; ++i) a.emplace_back(w[i], i);
    sort(a.begin(), a.end());
    int pr = 0, pl = 0;
    long long sum = 0;
    while(pr < n && sum < L) {
        sum += a[pr++].first;
        while(sum > L) sum -= a[pl++].first;
        if(L <= sum && sum <= R) break;
    }
    while(pl < n && sum > R) sum -= a[pl++].first;
    if(L <= sum && sum <= R) {
        for (int i = pl; i < pr; ++i) ans.push_back(a[i].second);
    }
    return ans;

}

#ifdef LOCAL

#include <cstdio>
#include <vector>
#include <cassert>

int main() {
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
    int n, l, u;
    assert(3 == scanf("%d %d %d", &n, &l, &u));
    std::vector<int> w(n);
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &w[i]));
    std::vector<int> result = find_subset(l, u, w);
    
    
    printf("%d\n", (int)result.size());
    for (int i = 0; i < (int)result.size(); i++)
        printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}

#endif // LOCAL

// Dream it. Wish it. Do it.

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