Submission #757902

#	Time	Username	Problem	Language	Result	Execution time	Memory
757902		SanguineChameleon	Hiring (IOI09_hiring)	C++17	64 / 100	1575 ms	14200 KiB

hiring

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct cand {
	int S, Q, orig_id, sorted_id;
};

struct result {
	int cnt;
	long long sum_num;
	long long sum_den;
	int last_id;

	result(): cnt(0), sum_num(0), sum_den(1), last_id(-1) {};

	result(int _cnt, long long _sum_num, long long _sum_den, int _last_id): cnt(_cnt), sum_num(_sum_num), sum_den(_sum_den), last_id(_last_id) {};
};

const int maxN = 5e5 + 20;
cand cands[maxN];
int N;
long long W;

bool cmp1(cand C1, cand C2) {
	return C1.S * C2.Q < C2.S * C1.Q;
}

bool cmp2(cand C1, cand C2) {
	return C1.Q < C2.Q;
}

bool cmp3(result res1, result res2) {
	if (res1.cnt != res2.cnt) {
		return res1.cnt < res2.cnt;
	}
	else {
		return res1.sum_num * res2.sum_den > res2.sum_num * res1.sum_den;
	}
}

void trace(result res) {
	cout << res.cnt << '\n';
	if (res.cnt == 0) {
		return;
	}
	set<pair<int, int>> s;
	for (int i = 1; i <= res.last_id; i++) {
		s.emplace(cands[i].Q, cands[i].orig_id);
	}
	long long lim = W * cands[res.last_id].Q / cands[res.last_id].S;
	long long sum = 0;
	for (auto p: s) {
		if (sum + p.first <= lim) {
			sum += p.first;
			cout << p.second << '\n';
		}
		else {
			break;
		}
	}
}

void just_do_it() {
	cin >> N >> W;
	for (int i = 1; i <= N; i++) {
		cin >> cands[i].S >> cands[i].Q;
		cands[i].orig_id = i;
	}
	sort(cands + 1, cands + N + 1, cmp1);
	multiset<int> s;
	result res;
	for (int i = 1; i <= N; i++) {
		s.insert(cands[i].Q);
		long long lim = W * cands[i].Q / cands[i].S;
		long long sum = 0;
		int cnt = 0;
		for (auto x: s) {
			if (sum + x <= lim) {
				sum += x;
				cnt++;
			}
			else {
				break;
			}
		}
		res = max(res, result(cnt, sum * cands[i].S, cands[i].Q, i), cmp3);
	}
	trace(res);
}

• Subtask 1: 30 / 30
• Subtask 2: 16 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6