Submission #752474

#	Time	Username	Problem	Language	Result	Execution time	Memory
752474		wenqi	Hiring (IOI09_hiring)	C++17	60 / 100	320 ms	12168 KiB

hiring

// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;

#ifdef DEBUG
#define D(args...) fprintf(stderr, args)
#else
#define D(...)
#endif

int N;
ll W;

struct Node
{
	int cnt;
	ll sum;
};

Node nodes[80005];

void upd(int i, int l, int r, int p)
{
	auto &node = nodes[i];
	if (p < l or p > r)
		return;
	if (l == r)
	{
		node.cnt++;
		node.sum += p;
		return;
	}
	int m = (l + r) / 2;
	upd(2 * i, l, m, p);
	upd(2 * i + 1, m + 1, r, p);
	node.cnt = nodes[2 * i].cnt + nodes[2 * i + 1].cnt;
	node.sum = nodes[2 * i].sum + nodes[2 * i + 1].sum;
}

pair<int, ll> query(int i, int l, int r, int scl, ll bound)
{
	auto &node = nodes[i];
	if (l == r)
	{
		auto k = min<ll>(node.cnt, bound / scl / l);
		return {k, k * l * scl};
	}
	int m = (l + r) / 2;
	auto &ln = nodes[2 * i];
	if (ln.sum * scl <= bound)
	{
		auto w = query(2 * i + 1, m + 1, r, scl, bound - ln.sum * scl);
		return {w.first + ln.cnt, w.second + ln.sum * scl};
	}
	return query(2 * i, l, m, scl, bound);
}

int main(int argc, const char *argv[])
{
	scanf(" %d %lld", &N, &W);
	vector<tuple<int, int, int>> p;
	for (int i = 1; i <= N; i++)
	{
		int s, q;
		scanf(" %d %d", &s, &q);
		p.push_back({s, q, i});
	}
	sort(p.begin(), p.end(),
	     [](auto &f, auto &s)
	     {
		     auto [a, b, i] = f;
		     auto [x, y, j] = s;
		     return a * y < b * x;
	     });
	int ans = 0;
	pair<ll, ll> frac;
	int marker = -1;
	for (auto [s, q, i] : p)
	{
		upd(1, 1, 20000, q);
		auto b = query(1, 1, 20000, s, W * q);
		if (b.first > ans)
		{
			ans = b.first;
			marker = i;
			frac = {b.second, q};
		}
		else if (b.first == ans and
			 (__int128_t) b.second * s * frac.second < (__int128_t)frac.first * q)
		{
			marker = i;
			frac = {b.second, q};
		}
	}
	printf("%d\n", ans);
	priority_queue<pair<int, int>> pq;
	for (auto [s, q, i] : p)
	{
		pq.push({q, i});
		while ((int)pq.size() > ans)
			pq.pop();
		if (i == marker)
		{
			while (pq.size())
			{
				printf("%d\n", pq.top().second);
				pq.pop();
			}
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main(int, const char**)':
hiring.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf(" %d %lld", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
hiring.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf(" %d %d", &s, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• 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