Submission #899812

#	Time	Username	Problem	Language	Result	Execution time	Memory
899812		josanneo22	Hiring (IOI09_hiring)	C++17	2 / 100	232 ms	18624 KiB

hiring

#pragma warning(suppress : 4996)
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

#define L(i,j,k) for(int i=j;i<=k;i++)
#define R(i,j,k) for(int i=j;i>=k;i--)

constexpr int _N = 5E5 + 500;

struct worker {
	int salary, qualifications, id;
	bool operator < (worker& b) {
		return salary * b.qualifications > b.salary * b.qualifications;
	}
}A[_N];													   
int cnt[_N], N; i64 W, buc[_N];
i64 T[_N];
void add(int x,int v) {
	while (x <= N) {
		T[x] += v;
		cnt[x]++;
		x += x & -x;
	}
}
pair<i64, int> query(i64 limit) {
	i64 sum = 0, total = 0, ind = 0;
	R(i, 18, 0) {
		int new_ind = ind + (1 << i);
		if (new_ind > N) continue;
		if (sum + T[new_ind] > limit) continue;
		ind = new_ind;
		sum += T[ind]; total += cnt[ind];
	}
	return make_pair(sum, total);
}
int main() {
	scanf("%d%d", &N, &W);
	L(i, 1, N) {
		scanf("%d%d", &A[i].salary, &A[i].qualifications);
		buc[A[i].qualifications]++;
		A[i].id = i;
	}
	sort(A + 1, A + 1 + N);
	L(i, 1, _N - 1) buc[i] += buc[i - 1];
	int starting_position = 0, best = -1;
	i64 old_fraction_top, old_fraction_bottom;
	R(i, N, 1) {
		int p = buc[A[i].qualifications]--;
		add(p, A[i].qualifications);
		auto res = query(W * A[i].qualifications / A[i].salary);
		i64 sum = res.first; int cnt = res.second;
		i64 cur_fraction_top = A[i].salary * sum;
		i64 cur_fraction_bottom = A[i].qualifications;
		if (cnt > best || (cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_bottom * cur_fraction_bottom)) {
			best = cnt;
			starting_position = i;
			old_fraction_bottom = cur_fraction_bottom;
			old_fraction_top = cur_fraction_top;
		}
	}
	sort(A + starting_position, A + N + 1, [&](auto& a, auto& b) {
		return a.qualifications < b.qualifications;
	});
	cout << best << '\n';
	L(i, 0, best - 1)	cout << A[starting_position + i].id << '\n';

}

Compilation message (stderr)

hiring.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(suppress : 4996)
      | 
hiring.cpp: In function 'int main()':
hiring.cpp:38:12: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'i64*' {aka 'long long int*'} [-Wformat=]
   38 |  scanf("%d%d", &N, &W);
      |           ~^       ~~
      |            |       |
      |            int*    i64* {aka long long int*}
      |           %lld
hiring.cpp:47:6: warning: variable 'old_fraction_top' set but not used [-Wunused-but-set-variable]
   47 |  i64 old_fraction_top, old_fraction_bottom;
      |      ^~~~~~~~~~~~~~~~
hiring.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~
hiring.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d", &A[i].salary, &A[i].qualifications);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:55:98: warning: 'old_fraction_bottom' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   if (cnt > best || (cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_bottom * cur_fraction_bottom)) {
      |                                                                              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 30
• Subtask 2: 0 / 28
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6