Submission #756453

#	Time	Username	Problem	Language	Result	Execution time	Memory
756453		borisAngelov	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	65 ms	8616 KiB

molecules

#include "molecules.h"

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 200005;

int n;

pair<long long, int> a[maxn];
long long preffix[maxn];

long long minv, maxv;

vector<int> find_subset(int inputl, int inputr, vector<int> weights)
{
    minv = inputl * 1LL;
    maxv = inputr * 1LL;
    n = weights.size();

    for (int i = 1; i <= n; ++i)
    {
        a[i].first = weights[i - 1] * 1LL;
        a[i].second = i - 1;
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        preffix[i] = preffix[i - 1] + a[i].first;
    }

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

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

            if (preffix[mid] - preffix[i - 1] >= minv)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        if (l == n + 1 || preffix[l] - preffix[i - 1] > maxv)
        {
            continue;
        }

        vector<int> result;

        for (int j = i; j <= l; ++j)
        {
            result.push_back(a[j].second);
        }

        sort(result.begin(), result.end());

        return result;
    }

    vector<int> dumb;

    return dumb;
}

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