제출 #764685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764685		zsombor	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	52 ms	8712 KiB

molecules

#include <iostream>
#include <algorithm>
#include <vector>
#include "molecules.h"
using namespace std;
using ll = long long;

int n, a, b, c;
vector <pair <ll, int>> v;
vector <ll> p(2e5, 0);
vector <int> ans;

ll sum(int l, int cnt) {
	if (l) return p[l + cnt - 1] - p[l - 1];
	return p[cnt - 1];
}

void solve(int cnt, ll r) {
	a = 0, b = n - cnt + 1;
	while (b - a > 1) {
		c = (a + b) / 2;
		(sum(c, cnt) <= r ? a = c : b = c);
	}
	ans.push_back(v[a].second);
	if (cnt > 1) solve(cnt - 1, r - v[a].first);
}

vector <int> find_subset(int l, int u, vector<int> w) {
	n = w.size();
	v.resize(n);
	for (int i = 0; i < n; i++) {
		v[i].first = w[i];
		v[i].second = i;
	}
	sort(v.begin(), v.end());
	p[0] = v[0].first;
	for (int i = 1; i < n; i++) p[i] = p[i - 1] + v[i].first;

	for (int i = 1; i <= n; i++) {
		if (sum(0, i) > u || sum(n - i, i) < l) continue;
		solve(i, u);
		sort(ans.begin(), ans.end());
		return ans;
	}
	return ans;
}

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