Submission #448443

#	Time	Username	Problem	Language	Result	Execution time	Memory
448443		_DaNeK_	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	69 ms	4036 KiB

molecules

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
#define bust ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = INT_MAX;
const int N = 2 * 1e5 + 10;
const ld eps = 1e-6;
const int mod = 1e9 + 7;

/*int a[N];*/

vector < int > find_subset(int l, int u, vector < int > w)
{
    int s = l, n = w.size();
    vector < pair < int , int > > tmp (n);
    for (int i = 0; i < n; ++i)
        tmp[i].fi = w[i], tmp[i].se = i;
    ll cursum = 0;
    l = 0;
    int r = 0;
    sort (tmp.begin(), tmp.end());
    sort (w.begin(), w.end());
    while (l < n)
    {
        while (r < n && cursum < s)
        {
            cursum += w[r];
            ++r;
        }
        if (cursum >= s && cursum <= u)
        {
            vector < int > result (r - l);
            for (int i = 0; i < r - l; ++i)
                result[i] = tmp[l + i].se;
            return result;
        }
        cursum -= w[l];
        ++l;
    }
    return {};
}

/*int main()
{
    bust
    int t = 1;
    //cin >> t;
    //scanf ("%d", &t);
    vector < int > res;
    while (t--)
        res = find_subset (4, 5, {3, 3, 3});
    cout << res.size() << "\n";
    return 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