Submission #1024943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024943		0npata	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	317 ms	4844 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector

const int MX = 500'005;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    //cat cerr << "ran" << '\n';
	vec<int> seq(MX, -1);

	int n = w.size();

	bitset<MX> pos;
	pos.set(0);

	for(int i = 0; i<w.size(); i++) {
		bitset<MX> npos = pos | (pos<<w[i]);
		bitset<MX> nset = npos & (~pos);

		for(int j = nset._Find_first(); j<MX; j=nset._Find_next(j)) {
		    seq[j] = i;
						//cerr << "stuck1" << '\n';
		}

		//cerr << "slow" << '\n';
		pos = npos;
	}

	int lst = -1;
	for(int i = l; i<=u; i++) {
	   if(seq[i] != -1) lst = i;
	}

	if(lst == -1) {
	return {};
	}

	vec<int> ans(0);
	while(lst != 0) {
	   assert(seq[lst] != -1);
        ans.push_back(seq[lst]);
    	lst -= w[seq[lst]];
	}

	reverse(ans.begin(), ans.end());
	return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i<w.size(); i++) {
      |                 ~^~~~~~~~~
molecules.cpp:14:6: warning: unused variable 'n' [-Wunused-variable]
   14 |  int n = w.size();
      |      ^

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