oj.uz

Submission #574411

# Submission time Handle Problem Language Result Execution time Memory
574411 2022-06-08T13:48:36 Z keta_tsimakuridze Hiring (IOI09_hiring) C++14
100 / 100
 592 ms 22884 KB 
#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";
	
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 6 ms 1400 KB Output is correct
11 Correct 8 ms 1556 KB Output is correct
12 Correct 8 ms 788 KB Output is correct
13 Correct 10 ms 1920 KB Output is correct
14 Correct 14 ms 1940 KB Output is correct
15 Correct 16 ms 1940 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 23 ms 2384 KB Output is correct
5 Correct 59 ms 4176 KB Output is correct
6 Correct 336 ms 14884 KB Output is correct
7 Correct 422 ms 19452 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1208 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7060 KB Output is correct
2 Correct 144 ms 7004 KB Output is correct
3 Correct 126 ms 7024 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 10904 KB Output is correct
2 Correct 228 ms 11032 KB Output is correct
3 Correct 200 ms 10996 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 20612 KB Output is correct
2 Correct 487 ms 20964 KB Output is correct
3 Correct 500 ms 20884 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 22736 KB Output is correct
2 Correct 592 ms 22812 KB Output is correct
3 Correct 590 ms 22884 KB Output is correct