Submission #715712

#	Time	Username	Problem	Language	Result	Execution time	Memory
715712		adrilen	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	1084 ms	2724 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
 
#include "molecules.h"
 
constexpr int maxu = 5e5 + 5;
 
int last[maxu] = { 0 };
 
bool found[maxu] = { 0 };
 
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    
    
    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: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31