Submission #467499

#	Time	Username	Problem	Language	Result	Execution time	Memory
467499		alextodoran	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	58 ms	6344 KiB

molecules

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

//#include "molecules.h"

using namespace std;

typedef long long ll;

vector <int> find_subset (int low, int high, vector <int> w)
{
    int n = (int) w.size();

    vector <int> p (n);
    for(int i = 0; i < n; i++)
        p[i] = i;
    sort(p.begin(), p.end(),
         [&] (const int &x, const int &y)
         {
             return w[x] < w[y];
         });

    vector <ll> pref (n);
    for(int i = 0; i < n; i++)
        pref[i] = w[p[i]];
    for(int i = 1; i < n; i++)
        pref[i] += pref[i - 1];

    function <ll (int, int)> seg = [&] (int l, int r)
    {
        return pref[r] - (l == 0 ? 0 : pref[l - 1]);
    };

    for(int len = 1; len <= n; len++)
        if(low <= seg(0, len - 1) && seg(0, len - 1) <= high)
        {
            vector <int> answer (len);
            for(int i = 0; i < len; i++)
                answer[i] = p[i];

            return answer;
        }
        else if(seg(0, len - 1) <= low && low <= seg(n - len, n - 1))
        {
            int pos = 0;
            while(seg(pos + 1, pos + len) < low)
                pos++;

            vector <int> answer (len);
            for(int i = 0; i < len; i++)
                answer[i] = pos + i;

            ll sum = seg(pos, pos + len - 1);

            int curr = len - 1;
            while(sum < low)
            {
                sum -= w[p[answer[curr]]];
                answer[curr]++;
                sum += w[p[answer[curr]]];

                curr--;
            }

            for(int i = 0; i < len; i++)
                answer[i] = p[answer[i]];

            return answer;
        }

    return {};
}

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