Submission #899814

#TimeUsernameProblemLanguageResultExecution timeMemory
899814josanneo22Hiring (IOI09_hiring)C++17
2 / 100
225 ms18516 KiB
#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%lld", &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 = 0, old_fraction_bottom = 0;
	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_top * 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:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%lld", &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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...