Submission #574405

#	Time	Username	Problem	Language	Result	Execution time	Memory
574405		Elias	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	3 ms	496 KiB

molecules

#include <bits/stdc++.h>

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include "molecules.h"
#endif

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w)
{
    int n = w.size();

    vector<pair<int, int>> a(n);

    for (int i = 0; i < n; i++)
        a[i] = {w[i], i};

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

    if (a[0].first > u)
        return {};
    if (a.back().first >= l && a.back().first <= u)
        return {n - 1};
    if (a[0].first >= l && a[0].first <= u)
        return {0};

    int i = 0;

    int sum = 0;
    for (int j = 0; j < n; j++)
    {
        sum += a[j].first;
        while (sum > u)
        {
            sum -= a[i].first;
            i++;
        }

        if (sum >= l)
        {
            vector<int> out;
            for (int k = i; k <= j; k++)
            {
                out.push_back(a[k].second);
            }
            return out;
        }
    }

    return {};
}

#ifdef _DEBUG

signed main()
{
    int n, l, u;
    cin >> n >> l >> u;

    vector<int> a(n);

    for (int &x : a)
        cin >> x;

    for (int x : find_subset(l, u, a))
        cout << x << " ";
}

#endif

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