Submission #366812

#	Time	Username	Problem	Language	Result	Execution time	Memory
366812		kostia244	Hiring (IOI09_hiring)	C++17	100 / 100	719 ms	39684 KiB

hiring

#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
const int maxn = 5e5 + 10;
struct frac : array<ll, 3> {
	frac(ll x, ll y, ll id) : array({x, y, id}) {}
	friend bool operator<(const frac &a, const frac &b) {
		return a[0]*b[1] < b[0]*a[1];
	}
};
int n, took, S[maxn], Q[maxn], so[maxn], fo[maxn];
vector<frac> fs;
vector<array<int, 2>> ss;
ll m, cur[maxn], cnt[maxn];
void add(int id) {
	for(int v = ss[id++][0]; id < maxn; id += id&-id) cnt[id]++, cur[id]+=v;
}
tuple<ll, frac, ll> ans = make_tuple<ll, frac, ll>(0, frac(0, 1, 0), 0);
void count(int v) {
	ll sm = 0, c = 0, p = 0;
	for(int i = 1<<19; i>>=1;)
		if(p+i < maxn && (sm+cur[p+i])*S[v] <= m*Q[v]) {
			p += i;
			sm += cur[p], c += cnt[p];
		}
	//cout << c << " " << sm << " " << v << endl;
	ans = max(ans, make_tuple<ll, frac, ll>(ll(c), frac(-sm*S[v], Q[v], 6969), v));
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> S[i] >> Q[i];
		fs.emplace_back(S[i], Q[i], i);
		ss.push_back({Q[i], i});
	}
	sort(all(fs)), sort(all(ss));
	for(int i = 0; i < ss.size(); i++) so[ss[i][1]] = i;
	for(int i = 0; i < ss.size(); i++) fo[fs[i][2]] = i;
	for(auto F: fs) {
		int id = F[2];
		add(so[id]);
		count(id);
	}
	cout << get<0>(ans) << '\n';
	ll s = S[get<2>(ans)], q = Q[get<2>(ans)];
	vector<int> ids;
	m *= q;
	for(auto [qi, id] : ss) {
		if(fo[id] > fo[get<2>(ans)]) continue;
		//cout << qi << "_" << endl;
		qi *= s;
		if(m >= qi) m -= qi, ids.push_back(id+1);
	}
	for(auto i : ids) cout << i << '\n';
} 

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0; i < ss.size(); i++) so[ss[i][1]] = i;
      |                 ~~^~~~~~~~~~~
hiring.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < ss.size(); i++) fo[fs[i][2]] = 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