Submission #588597

#	Time	Username	Problem	Language	Result	Execution time	Memory
588597		Drew_	Hiring (IOI09_hiring)	C++17	60 / 100	377 ms	15324 KiB

hiring

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

#define pb push_back
#define f1 first
#define s2 second
// #define int long long

using ll = long long;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

const int MAX = 5e5 + 69;

template<class T>
struct fenwick
{
	T bit[MAX];
	inline void add(int x, T val)
	{
		for (; x < MAX; x += (x & -x))
			bit[x] += val;
	}
	inline T sum(int x)
	{
		T res = 0;
		for (; x > 0; x -= (x & -x))
			res += bit[x];
		return res;
	}
};

int32_t main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	ll W;
	cin >> N >> W;

	vector<array<int, 4>> V(N);
	for (auto &[s, q, i, idx] : V)
		cin >> s >> q;
	for (int i = 0; i < N; ++i)
		V[i][3] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return x[1] < y[1];
	});

	for (int i = 0; i < N; ++i)
		V[i][2] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return 1ll * x[0] * y[1] < 1ll * y[0] * x[1];
	});

	fenwick<ll> bit1;
	fenwick<int> bit2;

	int res = 0, id = -1;
	for (int j = 0; j < N; ++j)
	{
		auto &[s, q, i, idx] = V[j];

		bit1.add(i, q);
		bit2.add(i, 1);

		int l = 0, r = N;
		while (l < r)
		{
			int mid = (l + r + 1) >> 1;
			if (bit1.sum(mid) * s <= 1ll * W * q) l = mid;
			else r = mid - 1;
		}

		if (bit2.sum(l) > res)
			res = bit2.sum(l), id = j;
	}

	sort(V.begin(), V.begin()+id+1, [](auto &x, auto &y){
		return x[1] < y[1];
	});

	cout << res << '\n';
	for (int i = 0; i < res; ++i)
		cout << V[i][3] << '\n';
	return 0;
}

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