oj.uz

답안 #328759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328759 2020-11-17T22:37:23 Z luciocf Hiring (IOI09_hiring) C++14
100 / 100
 375 ms 9308 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 8 ms 620 KB Output is correct
15 Correct 9 ms 620 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 12 ms 768 KB Output is correct
5 Correct 31 ms 1388 KB Output is correct
6 Correct 213 ms 5424 KB Output is correct
7 Correct 286 ms 7408 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 2280 KB Output is correct
2 Correct 79 ms 2280 KB Output is correct
3 Correct 79 ms 2280 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 3812 KB Output is correct
2 Correct 127 ms 3812 KB Output is correct
3 Correct 126 ms 3812 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 8240 KB Output is correct
2 Correct 321 ms 8028 KB Output is correct
3 Correct 324 ms 8028 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 9308 KB Output is correct
2 Correct 372 ms 9220 KB Output is correct
3 Correct 375 ms 9308 KB Output is correct