Submission #489730

#	Time	Username	Problem	Language	Result	Execution time	Memory
489730		Evang	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	1087 ms	40932 KiB

molecules

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

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define DIE exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;

#include "molecules.h"

vi find_subset(int l, int u, vi w){
	int sum = 0;
	for(int x: w)
		sum += x;
	vc<bool> pos(sum+1);
	vi a(sum+1);
	pos[0] = 1;
	for(int i = 0; i < w.size(); ++i)
		for(int j = sum - w[i]; j >= 0; --j)
			if(pos[j]&&!pos[j+w[i]]){
				pos[j+w[i]] = 1;
				a[j+w[i]] = i;
				if(l <= j + w[i] && j + w[i] <= u){
					vi ans;
					int cur = j + w[i];
					while(cur>0){
						ans.pb(a[cur]);
						cur -= w[a[cur]];
					}
					return ans;
				}
			}
	return vi();
}

Compilation message (stderr)

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

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