Submission #867196

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

molecules

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
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].val);
    }


    //whileul care ia un termen mare si il inlocuieste cu cv existent in sir, explicatii mai complicate deci nu scriu
    for (int j = n - 1; j >= i; j--)
    {
        if (l <= sum && sum <= u)
            break;
         int dif = u - sum;
        auto poz = Set.lower_bound(w[j].val - dif);
        if (poz == Set.end())
            break;
 
        sum= sum - *poz + w[j].val;
        Set.erase(poz);
        Set.insert(w[j].val);
    }
    
    //verificare daca ne putem incadra in termeni
    if (l <= sum && sum <= u)
    {
        auto p = Set.begin();
        for(i = 0; i < n; i++)
            if (w[i].val == *p)
            {
                result.push_back(w[i].poz);
                Set.erase(p);
                p = Set.begin();
            }
    }
    
    return result;
}


/*
int main()
{
    int n, u, l;
    cin>> n >> l >> u;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin>> v[i];

    vector<int> ans = find_subset(l, u, v);
    for (int i = 0; i < ans.size(); i++)
        cout<< ans[i] + 1 << " ";
    return 0;
}
*/

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