Submission #715711

#	Time	Username	Problem	Language	Result	Execution time	Memory
715711		adrilen	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	340 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

#include "molecules.h"

constexpr int maxu = 5e4 + 5;

int last[maxu] = { 0 };

bool found[maxu] = { 0 };

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    sort(w.begin(), w.end());
    
    found[0] = true;

    int highest = 0;

    int p;

    for (int v = 0; v < (int)w.size(); v++)
    {
        for (int i = min(highest, maxu - 2); i >= 0; i--)
        {
            if (!found[i]) continue;
            // cout << i << endl;
            if (i + w[v] >= maxu) continue;

            if (found[i + w[v]]) continue;

            found[i + w[v]] = true;
            last[i + w[v]] = v;

            if (l <= i + w[v] && i + w[v] <= u) {
                p = i + w[v];
                goto finish;
            }
        }
        highest += w[v];
    }

    return vector<int>{};

    finish:

    vector <int> output;

    // int i = 15;
    while (p != 0)
    {
        output.emplace_back(last[p]);
        // cout << "p" << p << endl;
        p -= w[last[p]];
    }

    return output;
}

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