Submission #328759

#	Time	Username	Problem	Language	Result	Execution time	Memory
328759		luciocf	Hiring (IOI09_hiring)	C++14	100 / 100	375 ms	9308 KiB

hiring

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 5e5+10;

int n;
ll w;

struct S
{
	int s, q, ind;
} a[maxn];

bool comp(S a, S b)
{
	return a.s*b.q < b.s*a.q;
}

int main(void)
{
	scanf("%d %lld", &n, &w);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &a[i].s, &a[i].q);
		a[i].ind = i;
	}

	sort(a+1, a+n+1, comp);

	int ans = 0, ans_ind = 0;

	priority_queue<pii> fila;

	ll soma = 0;
	double ans_soma = 0;

	for (int i = 1; i <= n; i++)
	{
		if (1ll*a[i].s > w) continue;

		fila.push({a[i].q, i});
		soma += 1ll*a[i].q;

		while (1ll*a[i].s*soma > 1ll*w*a[i].q)
		{
			soma -= 1ll*fila.top().ff;
			fila.pop();
		}

		if (fila.size() > ans || (fila.size() == ans && (1.00*a[i].s/a[i].q*soma) < ans_soma))
			ans = fila.size(), ans_soma = (1.00*a[i].s/a[i].q*soma), ans_ind = i;
	}

	printf("%d\n", ans);

	while (fila.size()) fila.pop();

	soma = 0;

	for (int i = 1; i <= n; i++)
	{
		if (1ll*a[i].s > w) continue;

		fila.push({a[i].q, i});
		soma += 1ll*a[i].q;

		while (1ll*a[i].s*soma > 1ll*w*a[i].q)
		{
			soma -= 1ll*fila.top().ff;
			fila.pop();
		}

		if (i == ans_ind)
		{
			while (fila.size())
			{
				printf("%d\n", a[fila.top().ss].ind);
				fila.pop();
			}

			return 0;
		}
	}
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |   if (fila.size() > ans || (fila.size() == ans && (1.00*a[i].s/a[i].q*soma) < ans_soma))
      |       ~~~~~~~~~~~~^~~~~
hiring.cpp:58:41: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |   if (fila.size() > ans || (fila.size() == ans && (1.00*a[i].s/a[i].q*soma) < ans_soma))
      |                             ~~~~~~~~~~~~^~~~~~
hiring.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%d %lld", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
hiring.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d %d", &a[i].s, &a[i].q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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