Submission #1002836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002836		Tob	Hiring (IOI09_hiring)	C++14	100 / 100	522 ms	31152 KiB

hiring

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const double prec = 1e-9;

int main () {
	ll n;
	double w;
	cin >> n >> w;
	
	vector <pair <pair <double, double>, int> > v;
	
	for (int i = 0; i < n; i++) {
		double a, b; cin >> a >> b;
		v.pb({{a/b, b}, i+1});
	}
	
	sort(all(v));
	
	set <pair <double, int> > s;
	int cnt = 0, res = 0, ix = 0;
	double sum = 0, msum = 1e13;
	
	for (int i = 0; i < v.size(); i++) {
		auto it = v[i];
		s.insert({it.F.S, it.S});
		double lim = w / it.F.F;
		sum += it.F.S;
		cnt++;
		while (sum - lim > prec) {
			auto p = s.end();
			--p;
			sum -= (*p).F;
			cnt--;
			s.erase(p);
		}
		if (cnt > res) {
			res = cnt;
			msum = sum * it.F.F;
			ix = i+1;
		}
		if (cnt == res && sum * it.F.F < msum) {
			msum = sum * it.F.F;
			ix = i+1;
		}
	}
	sum = 0;
	s.clear();
	
	cout << res << "\n";
	
	for (int i = 0; i < v.size(); i++) {
		auto it = v[i];
		s.insert({it.F.S, it.S});
		double lim = w / it.F.F;
		sum += it.F.S;
		cnt++;
		while (sum - lim > prec) {
			auto p = s.end();
			--p;
			sum -= (*p).F;
			cnt--;
			s.erase(p);
		}
		if (i+1 == ix) {
			for (auto itt : s) {
				cout << itt.S << "\n";
			}
			break;
		}
	}
	
	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
hiring.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

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