Submission #394537

#	Time	Username	Problem	Language	Result	Execution time	Memory
394537		ruadhan	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	4 ms	588 KiB

molecules

#include <bits/stdc++.h>
typedef long long ll;
#define sz(x) (int)x.size()
using namespace std;
typedef pair<int, int> pi;

vector<int> find_subset(int l, int u, vector<int> ww)
{
    int n = sz(ww);
    vector<pair<int, int>> w;
    for (int i = 0; i < (int)ww.size(); i++)
    {
        w.push_back({ww[i], i});
    }
    sort(w.begin(), w.end());
    // for (auto x : w)
    //     cout << x.first << " ";
    // cout << '\n';
    int i = 0, j = 0;
    ll sum = w[0].first;
    while (j < n)
    {
        // cout << "i = " << i << ", j = " << j << '\n';
        // cout << "sum = " << sum << '\n';
        int orig_j = j;
        while (j + 1 < n && sum < l)
        {
            j++;
            sum += w[j].first;
        }
        // if (j == n - 1 && i == n - 2)
        //     break;
        while (i + 1 < n && i + 1 <= j && sum > u)
        {
            sum -= w[i].first;
            i++;
        }
        if (sum >= l && sum <= u)
        {
            break;
            // cout << "found good answer"
            //  << ", sum = " << sum << '\n';
        }
        j += (orig_j == j ? 1 : 0);
    }
    vector<int> ans;
    if (sum >= l && sum <= u)
    {
        for (int k = i; k <= j; k++)
        {
            // cout << w[k].first << " ";
            ans.push_back(w[k].second);
        }
    }
    // cout << '\n';
    sort(ans.begin(), ans.end());
    return ans;
}

// int main()
// {
//     int l, u;
//     cin >> l >> u;
//     vector<int> a;
//     int tmp;
//     while (cin >> tmp)
//     {
//         a.push_back(tmp);
//     }
//     // auto ret = find_subset(15, 17, {6, 8, 8, 7});
//     // auto ret = find_subset(14, 15, {5, 5, 6, 6});
//     // auto ret = find_subset(10, 20, {15, 17, 16, 18});
//     auto ret = find_subset(l, u, a);
//     for (auto x : ret)
//         cout
//             << x << " ";
//     cout << '\n';
//     return 0;
// }

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