제출 #574411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574411		keta_tsimakuridze	Hiring (IOI09_hiring)	C++14	100 / 100	592 ms	22884 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t;
pair<int, ll> tree[4 * N];
void upd(int u,int id, int l,int r,int val) {
	if(l > id || r < id) return;
	if(l == r) {
		tree[u].f += val;
		tree[u].s += (ll)val * l;
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, id, l, mid, val); upd(2 * u + 1, id,mid + 1, r, val);
	tree[u].f = tree[2 * u].f + tree[2 * u + 1].f;
	tree[u].s = tree[2 * u].s + tree[2 * u + 1].s;
}
pair<int,ll> get(int u,int k,int l,int r) {
	if(l == r) {
		return {min(tree[u].f, k / l), (ll)min(tree[u].f, k / l) * l};
	}
	int mid = (l + r) / 2; //cout << l << "_" << r << " " << tree[2 * u].s << endl;
	if(tree[2 * u].s >= k) return get(2 * u, k, l, mid);
	pair<int, ll> p = get(2 * u + 1, k - tree[2 * u].s, mid + 1, r);
	return {p.f + tree[2 * u].f, tree[2 * u].s + p.s};
}
main() {
	int n, W;
	cin >> n >> W;
	int M = 20000;
	vector<pair<double, pair<pii, int> > > v;
	for(int i = 1; i <= n; i++) {
		int s, q; cin >> s >> q;
		v.push_back({(double)s/(double)q, {{s, q}, i}});
		upd(1, q, 1, M, 1);
	}
	sort(v.rbegin(), v.rend());
	pair<int, pair<long double, int> >  ans;
	ans = {0, {0, 0}};
	for(int i = 0; i < n; i++) {
		double k = v[i].f;
		int s = v[i].s.f.f, q = v[i].s.f.s ;
		upd(1, q, 1, M, -1);
		pii p = get(1, (int)(W - s) / k, 1, M);  
		if(W >= s)
		ans = max(ans, {p.f + 1, {-(long double)p.s * k - s, i}});
		
	}
	vector<pii> x;
	for(int i = ans.s.s + 1; i < n; ++i) {
		x.push_back({v[i].s.f.s, v[i].s.s});
	}
	sort(x.begin(), x.end());
	cout << ans.f << endl;
	for(int i = 0; i + 1 < ans.f; i++) cout << x[i].s <<"\n";
	cout << v[ans.s.s].s.s << "\n";
	
}

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main() {
      | ^~~~

• 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