Submission #874696

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

molecules

#include <bits/stdc++.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 <int> ind(n);
    iota(ind.begin(), ind.end(), 0);
    sort(ind.begin(), ind.end(), [&] (const int &i, const int &j) {
        return w[i] < w[j];
    });
    vector <long long> pref(n);
    REP(i, n) {
        pref[i] = (i == 0 ? 0 : pref[i - 1]) + w[ind[i]];
    }


    auto get_pref = [&] (int l, int r) -> long long {
        return pref[r] - (l == 0 ? 0 : pref[l - 1]);
    };
    int k;
    REP(i, n) {
        if(pref[i] <= R && get_pref(n - i - 1, n - 1) >= L) {
            k = i + 1;
            break;
        }
    }
    vector <int> ans;
    long long sum = pref[k - 1];
    FORE(i, k - 1, n) {
        if(sum >= L && sum <= R) {
            FOR(j, i - k + 1, i) ans.emplace_back(ind[j]);
            break;
        }
        sum -= w[ind[i - k + 1]];
        if(i + 1 < n) sum += w[ind[i + 1]];
    }
    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.

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:42:28: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |     long long sum = pref[k - 1];
      |                          ~~^~~

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