Submission #920918

#	Time	Username	Problem	Language	Result	Execution time	Memory
920918		danikoynov	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	39 ms	10032 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

int n;
vector < pair < ll, int > > values;
ll pref[maxn];
ll get_pref(int l, int r)
{
    ll val = pref[r];
    if (l != 0)
        val -= pref[l - 1];
    return val;
}

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
    n = w.size();
    for (int i = 0; i < n; i ++)
    {
        values.push_back({w[i], i});
    }
    sort(values.begin(), values.end());
    for (int i = 0; i < n; i ++)
    {
        if (i != 0)
            pref[i] = pref[i - 1];
        pref[i] += values[i].first;
    }

    for (int len = 1; len <= n; len ++)
    {
        ll bot = get_pref(0, len - 1);
        ll top = get_pref(n - len, n - 1);
        //cout << "len " << len << " " << bot << " " << top << endl;
        if (bot > u)
        {
            vector < int > res;
            return res;
        }

        if (bot >= l)
        {

            vector < int > res;
            for (int i = 0; i < len; i ++)
                res.push_back(values[i].second);
            return res;
        }

        if (top >= l)
        {
            ll sum = bot;
            int pt = len;
            while(pt < n)
            {
                sum += values[pt].first;
                sum -= values[pt - len].first;
                if (sum >= l)
                {
                    //cout << "here" << endl;
                    vector < int > res;
                    for (int i = pt - len + 1; i <= pt; i ++)
                        res.push_back(values[i].second);
                    return res;
                }
                pt ++;
            }
            assert(false);
        }
    }
    vector < int > vec;
    return vec;

    assert(false);
    cout << "wtf" << endl;
    exit(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