Submission #1036551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036551		kunzaZa183	Hiring (IOI09_hiring)	C++17	2 / 100	487 ms	65536 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
#define int long long
const double db = 1e-5;
const int maxn = 500001;
int orig[maxn], quality[maxn];
double seg[maxn * 4], adjusted[maxn];
int segppl[maxn * 4];
void update(int curin, int curl, int curr, int in, double val, int ppl) {
	if (in < curl || curr < in) return;
	if (curl == curr) {
		seg[curin] = val;
		segppl[curin] = ppl;
		return;
	}
	update(curin * 2 + 1, curl, (curl + curr) / 2, in, val, ppl);
	update(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val, ppl);
	seg[curin] = seg[curin * 2 + 1] + seg[curin * 2 + 2];
	segppl[curin] = segppl[curin * 2 + 1] + segppl[curin * 2 + 2];
}
struct kun {
	int orderin, rightmost, sumprice, numofppl;
	kun() {
		orderin = 0, rightmost = -1, sumprice = 0, numofppl = 0;
	}
};
void query(int curin, int curl, int curr, double val, kun& tmp) {
	if (val >= seg[curin] - db) {
		tmp.rightmost = max(tmp.rightmost, curr);
		tmp.sumprice += seg[curin];
		tmp.numofppl += segppl[curin];
		return;
	}
	if (curl == curr) {
		tmp.rightmost = max(tmp.rightmost, curr - 1);
		return;
	}
	if (val <= seg[curin * 2 + 1] + db)
		return query(curin * 2 + 1, curl, (curl + curr) / 2, val, tmp);
	tmp.sumprice += seg[curin * 2 + 1];
	tmp.numofppl += segppl[curin * 2 + 1];
	return query(curin * 2 + 2, (curl + curr) / 2 + 1, curr,
		val - seg[curin * 2 + 1], tmp);
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n, budget;
	cin >> n >> budget;
	int maxsecond = 0;
	for (int i = 0; i < n; i++) {
		cin >> orig[i] >> quality[i];
		maxsecond = max(maxsecond, quality[i]);
	}
	for (int i = 0; i < n; i++) adjusted[i] = orig[i] * maxsecond / double(quality[i]);
	vector<int> vi(n);
	iota(vi.begin(), vi.end(), 0);
	vector<int> ordervi(vi);
	sort(vi.begin(), vi.end(),
		[&](int a, int b) { return adjusted[a] < adjusted[b]; });
	for (int i = 0; i < n; i++) update(0, 0, n - 1, i, adjusted[vi[i]], 1);

	sort(ordervi.begin(), ordervi.end(), [&](int a, int b) {
		if (quality[a] != quality[b]) return quality[a] > quality[b];
		return orig[a] > orig[b];
		});

	vector<int> where(n);
	for (int i = 0; i < n; i++) where[vi[i]] = i;

	vector<kun> vtiii;
	for (int i = 0; i < n; i++) {
		update(0, 0, n - 1, where[ordervi[i]], 0, 0);
		kun tmp;
		tmp.orderin = i;
		tmp.sumprice = adjusted[ordervi[i]];
		tmp.numofppl = 1;
		query(0, 0, n - 1, double(budget) * maxsecond / quality[ordervi[i]] - adjusted[ordervi[i]], tmp);
		tmp.sumprice *= double(quality[ordervi[i]]) / maxsecond;
		vtiii.push_back(tmp);
	}
	auto tmp = *max_element(vtiii.begin(), vtiii.end(), [&](kun a, kun b) {
		if (a.numofppl != b.numofppl)
			return a.numofppl < b.numofppl;
		return a.sumprice > b.sumprice;
		});
	set<int> si;
	set<int> cannot;
	for (int i = 0; i < tmp.orderin; i++) cannot.insert(ordervi[i]);
	for (int i = 0; i <= tmp.rightmost; i++)
		if (!cannot.count(vi[i])) si.insert(vi[i]);
	si.insert(ordervi[tmp.orderin]);
	cout << si.size() << "\n";
	for (auto a : si) cout << a + 1 << "\n";
}

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