제출 #757903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757903		SanguineChameleon	Hiring (IOI09_hiring)	C++17	100 / 100	595 ms	50384 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];
pair<long long, int> tree[maxN * 4];
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 update(int id, int lt, int rt, int pos, int val) {
	if (lt == rt) {
		tree[id] = make_pair(val, 1);
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, val);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, val);
	}
	tree[id].first = tree[id * 2].first + tree[id * 2 + 1].first;
	tree[id].second = tree[id * 2].second + tree[id * 2 + 1].second;
}

pair<long long, int> get(int id, int lt, int rt, long long lim) {
	if (lt == rt) {
		if (tree[id].second == 1 && tree[id].first <= lim) {
			return tree[id];
		}
		else {
			return make_pair(0, 0);
		}
	}
	int mt = (lt + rt) / 2;
	if (tree[id * 2].first > lim) {
		return get(id * 2, lt, mt, lim);
	}
	else {
		auto p = get(id * 2 + 1, mt + 1, rt, lim - tree[id * 2].first);
		p.first += tree[id * 2].first;
		p.second += tree[id * 2].second;
		return p;
	}
}

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, cmp2);
	for (int i = 1; i <= N; i++) {
		cands[i].sorted_id = i;
	}
	sort(cands + 1, cands + N + 1, cmp1);
	result res;
	for (int i = 1; i <= N; i++) {
		update(1, 1, N, cands[i].sorted_id, cands[i].Q);
		long long lim = W * cands[i].Q / cands[i].S;
		auto p = get(1, 1, N, lim);
		long long sum = p.first;
		int cnt = p.second;
		res = max(res, result(cnt, sum * cands[i].S, cands[i].Q, i), cmp3);
	}
	trace(res);
}

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