Submission #915006

#	Time	Username	Problem	Language	Result	Execution time	Memory
915006		vjudge1	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	8 ms	604 KiB

molecules

#include "molecules.h"

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

using Bitset = bitset<10010>;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
        int n = w.size();
        Bitset knapsack;
        knapsack[0] = -1;
        vector<int> first_on(10010, -2);
        for (int j = 0; j < n; j++) {
                int v = w[j];
                Bitset new_knapsack = knapsack | (knapsack << v);
                Bitset tmp = new_knapsack ^ knapsack;
                while (tmp.any()) {
                        int i = tmp._Find_first();
                        first_on[i] = j;
                        tmp[i] = 0;
                }
                knapsack = new_knapsack;
        }
        for (int i = l; i <= u; i++) {
                if (first_on[i] != -2) {
                        vector<int> ans;
                        for (int j = first_on[i]; i != 0; j = first_on[i]) {
                                ans.push_back(j);
                                i -= w[j];
                        }
                        return ans;
                }
        }
        return vector<int>();
}

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