Submission #219188

#	Time	Username	Problem	Language	Result	Execution time	Memory
219188		emil_physmath	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	66 ms	8696 KiB

molecules

#include "molecules.h"
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
using llong = long long;
const int maxN = 200000;
struct Int
{
    llong num;
    int ind;
    operator llong&() { return num; }
    operator const llong&() const { return num; }
};

llong pref[maxN];

inline llong Sum(int l, int r) { return pref[r] - (l ? pref[l - 1] : 0); }
vector<int> find_subset(int l, int u, vector<int> a)
{
    int m = a.size();
    vector<Int> w(m);
    for (int i = 0; i < m; ++i)
        w[i] = {a[i], i};
    sort(w.begin(), w.end());
    for (int i = 0; i < m; ++i)
        pref[i] = (i ? pref[i - 1] : 0) + w[i];
    for (int n = 1; n <= m; ++n)
    {
        llong mnsum = pref[n - 1], mxsum = Sum(m - n, m - 1);
        if (mnsum <= u && l <= mxsum)
        {
            for (int i = 0; i + n - 1 < m; ++i)
                if (l <= Sum(i, i + n - 1) && Sum(i, i + n - 1) <= u)
                {
                    vector<int> res;
                    for (int j = i; j <= i + n - 1; ++j)
                        res.push_back(w[j].ind);
                    return res;
                }
        }
    }
    return vector<int>(0);
}

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