Submission #328756

#	Time	Username	Problem	Language	Result	Execution time	Memory
328756		luciocf	Hiring (IOI09_hiring)	C++14	40 / 100	1590 ms	6508 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;

	priority_queue<pii> fila;

	ll soma = 0;
	double soma_s = 0, ans_soma = 0;

	vector<int> V;

	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;
		soma_s += 1.00*a[i].s;

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

		if (fila.size() > ans || (fila.size() == ans && soma_s < ans_soma))
		{
			ans = fila.size(), ans_soma = soma_s;
			V.clear();

			while (!fila.empty())
			{
				V.push_back(fila.top().ss);
				fila.pop();
			}

			for (auto x: V)
				fila.push({a[x].q, x});
		}
	}

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

	assert(ans == V.size());

	for (auto x: V)
		printf("%d\n", a[x].ind);
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:62: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]
   62 |   if (fila.size() > ans || (fila.size() == ans && soma_s < ans_soma))
      |       ~~~~~~~~~~~~^~~~~
hiring.cpp:62: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]
   62 |   if (fila.size() > ans || (fila.size() == ans && soma_s < ans_soma))
      |                             ~~~~~~~~~~~~^~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from hiring.cpp:1:
hiring.cpp:80:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  assert(ans == V.size());
      |         ~~~~^~~~~~~~~~~
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: 21 / 30
• Subtask 2: 10 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6