Submission #916115

#	Time	Username	Problem	Language	Result	Execution time	Memory
916115		IBory	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	39 ms	8152 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

vector<int> find_subset(int L, int R, vector<int> W) {
	vector<pii> P;
	ll low = 0, high = 0, N = W.size(), SZ = -1;

	for (int i = 0; i < N; ++i) P.emplace_back(W[i], i);
	sort(P.begin(), P.end());
	
	for (int i = 0; i < N; ++i) {
		low += P[i].first; high += P[N - 1 - i].first;
		if (L - high <= 0 && 0 <= R - low) {
			SZ = i + 1;
			break;
		}
	}

	vector<int> ret;
	if (SZ == -1) return ret;

	ll cur = 0;
	for (int i = 0; i < SZ; ++i) cur += P[i].first;
	if (L <= cur && cur <= R) {
		for (int i = 0; i < SZ; ++i) ret.push_back(P[i].second);
		return ret;
	}

	for (int n = 0; n < SZ; ++n) {
		cur += P[N - 1 - n].first - P[n].first;
		if (L <= cur && cur <= R) {
			for (int i = n + 1; i < SZ; ++i) ret.push_back(P[i].second);
			for (int i = 0; i <= n; ++i) ret.push_back(P[N - 1 - i].second);
			return ret;
		}
	}
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:8:14: warning: control reaches end of non-void function [-Wreturn-type]
    8 |  vector<pii> P;
      |              ^

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