Submission #867559

#	Time	Username	Problem	Language	Result	Execution time	Memory
867559		StefanL2005	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	348 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct comp{
    int poz, val;
};
bool rule(comp A, comp B)
{
    if (A.val == B.val)
        return A.poz < B.poz;
    return A.val < B.val;
}

vector<int> find_subset(int l, int u, vector<int> v)
{
    int n = v.size();
    set<int> Set;
    vector<int> result;
    vector<comp> w(n);

    for (int i = 0; i < n; i++)
    {
        w[i].val = v[i];
        w[i].poz = i;
    }
    sort(w.begin(), w.end(), rule);
 
    //base conditions
    if(u < w[0].val)
        return result;
    if (u - l < w[n-1].val - w[0].val)
        return result;

    //closest partial sum to u
    ll sum = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        if (sum + w[i].val > u)
            break;
        
        sum+= w[i].val;
        Set.insert(w[i].poz);
    }

    for (int j = n - 1; j >= i; j--)
    {
        if (l <= sum && sum <= u)
            break;

        auto poz = Set.begin();
        sum= sum - v[*poz] + w[j].val;
        Set.erase(poz);
        Set.insert(w[j].poz);
    }
    
    //verificare daca ne putem incadra in termeni
    if (l <= sum && sum <= u)
    {
        for (auto p = Set.begin(); p != Set.end(); p++)
        {
            result.push_back(*p);
            Set.erase(p);
        }
    }
    
    return result;
}

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