Submission #1293880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293880		loiloiloi	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	34 ms	4320 KiB

molecules

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
	return uniform_int_distribution<long long>(l, r)(rd);
}
std::vector<int> find_subset_brute(int l, int u, std::vector<int> w) {
	int n = sz(w);
	for (int mask = 0; mask < (1 << n); ++mask) {
		int sumw = 0;
		for (int i = 0; i < n; ++i) {
			if (mask >> i & 1) sumw += w[i];
		}
		if (sumw < l || sumw > u) continue;
		vi ans;
		for (int i = 0; i < n; ++i) {
			if (mask >> i & 1) ans.push_back(i);
		}
		return ans;
	}
    return std::vector<int>(0);
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int n = (int)w.size();
	vector<pii> W(n);
	for (int i = 0; i < n; i++) W[i] = {w[i], i};
	sort(begin(W), end(W), greater<pii>());
	
	deque<int> ans;
	long long cumsum = 0;
	int i = 0;
	while(i < n && cumsum < l) {
		cumsum += W[i].first;
		ans.push_back(W[i].second);
		i++;
	}
	if (cumsum < l)
    	return std::vector<int>(0);
    	
	if (cumsum <= u)
		return vi(begin(ans), end(ans)); 
		
	while(i < n) {
		cumsum += W[i].first;
		cumsum -= w[ans.front()];
		ans.pop_front();
		ans.push_back(W[i].second);
		// cerr << i << ' ' << cumsum << '\n';
		if (cumsum <= u) 
			return vi(begin(ans), end(ans));
		i++;
	}
	// cerr << "cc\n";
    return std::vector<int>(0);
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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