Submission #366789

#	Time	Username	Problem	Language	Result	Execution time	Memory
366789		kostia244	Hiring (IOI09_hiring)	C++17	74 / 100	452 ms	42496 KiB

hiring

#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(int x, int y, int 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;
}
array<ll, 3> ans {0, 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];
		}
	ans = max(ans, array<ll,3>{c, -sm, 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 << ans[0] << '\n';
	ll s = S[ans[2]], q = Q[ans[2]];
	vector<int> ids;
	m *= q;
	for(auto [qi, id] : ss) {
		if(fo[id] > fo[ans[2]]) continue;
		//cout << id << 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:38: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]
   38 |  for(int i = 0; i < ss.size(); i++) so[ss[i][1]] = i;
      |                 ~~^~~~~~~~~~~
hiring.cpp:39: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]
   39 |  for(int i = 0; i < ss.size(); i++) fo[fs[i][2]] = i;
      |                 ~~^~~~~~~~~~~

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