Submission #899802

#	Time	Username	Problem	Language	Result	Execution time	Memory
899802		josanneo22	Hiring (IOI09_hiring)	C++17	0 / 100	151 ms	14164 KiB

hiring

#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, 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() {
	memset(cnt,0,sizeof(cnt));
	memset(buc,0,sizeof(buc));
	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 = 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 new_cnt = res.second;
		i64 cur_fraction_top = A[i].salary * sum;
		i64 cur_fraction_bottom = A[i].qualifications;
		if (new_cnt > best || (new_cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_top * cur_fraction_bottom)) {
			best = new_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;
	});
	printf("%d", best);
	L(i, 0, best - 1) printf("%d\n", A[starting_position + i].id);
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~
hiring.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &A[i].salary, &A[i].qualifications);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 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