Submission #1351895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351895		bbbiros	Detecting Molecules (IOI16_molecules)	C++20	19 / 100	1095 ms	636 KiB

molecules

#include "molecules.h"
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
map<int, int> m;
vector<int> find_subset(int l, int u, vector<int> w)
{
    m[0] = -1;
    queue<int> q;
    q.push(0);
    int ans = 0;
    while (q.size())
    {
        int c = q.front();
        //cout << c << endl;
        q.pop();
        if (c >= l)
        {
            ans = c;
            break;
        }
        for (int i = m[c] + 1; i < w.size(); i++)
        {
            if (c + w[i] > u)
                continue;
            if (m.count(c + w[i])&&m[c+w[i]]<i)
                continue;
            m[c + w[i]] = i;
            q.push(c + w[i]);
        }
    }
    if (ans == 0)
        return {};
    vector<int> ansv;
    while (ans > 0)
    {
        ansv.push_back(m[ans]);
        ans -= w[ansv.back()];
    }
    reverse(ansv.begin(),ansv.end());
    return ansv;
}

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