Submission #393851

#	Time	Username	Problem	Language	Result	Execution time	Memory
393851		Berted	Hiring (IOI09_hiring)	C++14	34 / 100	179 ms	24396 KiB

hiring

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

#define ll long long
#define pii pair<ll, ll>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;

const int SZ = (1 << 15);

int N, cnt[20001]; ll K;
ppi A[500001];

inline bool comp(const ppi &L, const ppi &R) {return L.fst.fst * R.fst.snd < L.fst.snd * R.fst.fst;}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++) {cin >> A[i].fst.fst >> A[i].fst.snd; A[i].snd = i;}
	sort(A, A + N, comp);

	int j = 0, c = 0, best = -1, bestIdx = -1; pii bestFrac = {-1, 1}; ll S = 0;
	for (int i = 0; i < N; i++)
	{
		cnt[A[i].fst.snd]++;
		if (A[i].fst.snd <= j) {S += A[i].fst.snd; c++;}
		//cerr << S << "\n";
		for (; j < 20000 && (S + (ll)(j + 1) * cnt[j + 1]) * A[i].fst.fst <= A[i].fst.snd * K; j++)
		{
			S += (ll)(j + 1) * cnt[j + 1];
			c += cnt[j + 1];
		}
		for (; j && S * A[i].fst.fst > A[i].fst.snd * K; j--) 
		{
			S -= (ll)j * cnt[j];
			c -= cnt[j];
		}
		//cerr << i << ": " << A[i].fst.fst << " " << A[i].fst.snd << " " << j << "\n";
		int tp = (A[i].fst.snd * K - A[i].fst.fst * S) / (A[i].fst.fst * (ll)(j + 1)), t = c + tp;
		pii f = {(A[i].fst.snd * K - A[i].fst.fst * (S + tp * (j + 1))), A[i].fst.snd};
		if ((t > best) || (t == best && f.fst * bestFrac.snd > f.snd * bestFrac.fst)) {best = t; bestFrac = f; bestIdx = i;}
	}

	pii frac = A[bestIdx].fst;
	for (int i = 0; i <= bestIdx; i++) {A[i].fst.fst = A[i].fst.snd; A[i].fst.snd = A[i].snd;}
	sort(A, A + bestIdx + 1);
	
	S = 0;
	vector<int> ans;

	for (int i = 0; i <= bestIdx; i++)
	{
		S += A[i].fst.fst;
		if (K * frac.snd < frac.fst * S) {break;}
		else {ans.push_back(A[i].snd + 1);}
	}

	//cerr << "B:" << best << "\n";

	assert(best == ans.size());
	cout << best << "\n";
	for (const int &x : ans) cout << x << "\n";
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from hiring.cpp:4:
hiring.cpp: In function 'int main()':
hiring.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  assert(best == ans.size());
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 18 / 30
• Subtask 2: 16 / 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