Submission #289179

#	Time	Username	Problem	Language	Result	Execution time	Memory
289179		Kastanda	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	65 ms	7548 KiB

molecules

// M
#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
typedef long long ll;
const int N = 200005;
int n;
pair < int , int > W[N];
ll P[N], S[N];
vector < int > find_subset(int l, int u, vector < int > _W)
{
        n = (int)_W.size();
        for (int i = 1; i <= n; i ++)
                W[i].first = _W[i - 1], W[i].second = i - 1;

        sort(W + 1, W + n + 1);
        for (int i = 1; i <= n; i ++)
                P[i] = P[i - 1] + W[i].first;
        for (int i = n; i; i --)
                S[i] = S[i + 1] + W[i].first;

        for (int k = 1; k <= n; k ++)
                if (P[k] <= u && S[n - k + 1] >= l)
                {
                        ll SM = P[k];
                        int le = 1, ri = n;
                        while (SM < l)
                                SM += W[ri].first - W[le].first, ri --, le ++;
                        vector < int > Rs;
                        for (int i = le; i <= k; i ++)
                                Rs.push_back(W[i].second);
                        for (int i = ri + 1; i <= n; i ++)
                                Rs.push_back(W[i].second);
                        return Rs;
                }
        return vector < int > {};
}

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