Submission #1293868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293868		loiloiloi	Detecting Molecules (IOI16_molecules)	C++20	9 / 100	2 ms	348 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(int l, int u, std::vector<int> w) {
	int i = 0, 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;
	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()].first;
		ans.pop_front();
		ans.push_back(W[i].second);
		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: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31