oj.uz

Submission #752475

# Submission time Handle Problem Language Result Execution time Memory
752475 2023-06-03T04:42:22 Z wenqi Hiring (IOI09_hiring) C++17
100 / 100
 343 ms 12104 KB 
// 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 * 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

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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 4 ms 1236 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 6 ms 1576 KB Output is correct
14 Correct 9 ms 1556 KB Output is correct
15 Correct 9 ms 1660 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 13 ms 1732 KB Output is correct
5 Correct 29 ms 1944 KB Output is correct
6 Correct 186 ms 7308 KB Output is correct
7 Correct 243 ms 10164 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3696 KB Output is correct
2 Correct 88 ms 3636 KB Output is correct
3 Correct 78 ms 3680 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 5644 KB Output is correct
2 Correct 117 ms 5688 KB Output is correct
3 Correct 125 ms 5704 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 10920 KB Output is correct
2 Correct 283 ms 10992 KB Output is correct
3 Correct 304 ms 10952 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 12100 KB Output is correct
2 Correct 343 ms 12104 KB Output is correct
3 Correct 320 ms 12072 KB Output is correct