# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
892649 |
2023-12-25T16:09:01 Z |
Macker |
Hiring (IOI09_hiring) |
C++17 |
|
243 ms |
20484 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
struct node {
int cnt = 0; ld val = 0;
};
const int len = 32768;
vector<node> st(len * 2);
void add(int idx, ld val, int i = 1, int s = 0, int e = len){
if(idx >= e || idx < s) return;
if(idx == s && s + 1 == e) {
st[i].val += val;
st[i].cnt++;
return;
}
add(idx, val, i * 2, s, (s + e) / 2);
add(idx, val, i * 2 + 1, (s + e) / 2, e);
st[i].val = st[i * 2].val + st[i * 2 + 1].val;
st[i].cnt = st[i * 2].cnt + st[i * 2 + 1].cnt;
}
int walk(ld b, ld m, int i = 1){
if(i >= len){
if(st[i].val * m <= b) return st[i].cnt;
else return 0;
}
if(st[i * 2].val * m <= b) return st[i * 2].cnt + walk(b - st[i * 2].val * m, m, i * 2 + 1);
else return walk(b, m, i * 2);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, b; cin >> n >> b;
vector<pair<ld, int>> v;
for (int i = 0; i < n; i++) {
int c, q; cin >> c >> q;
v.push_back({(ld)c / (ld)q, q});
}
sort(all(v));
int mx = 0, mxi;
for (int i = 0; i < n; i++) {
auto& [x, q] = v[i];
add(q, q);
int ret = walk(b, x);
if(ret > mx){
mx = ret;
mxi = i;
}
}
cout << mx << "\n";
for (int i = 0; i < mx; i++)
cout << 0 << "\n";
}
Compilation message
hiring.cpp: In function 'int main()':
hiring.cpp:52:17: warning: variable 'mxi' set but not used [-Wunused-but-set-variable]
52 | int mx = 0, mxi;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
2 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
3 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
4 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
5 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
6 |
Partially correct |
2 ms |
2648 KB |
Partially correct |
7 |
Partially correct |
2 ms |
2652 KB |
Partially correct |
8 |
Partially correct |
3 ms |
2652 KB |
Partially correct |
9 |
Partially correct |
3 ms |
2908 KB |
Partially correct |
10 |
Incorrect |
3 ms |
2908 KB |
Output isn't correct |
11 |
Partially correct |
4 ms |
2784 KB |
Partially correct |
12 |
Partially correct |
5 ms |
2784 KB |
Partially correct |
13 |
Partially correct |
6 ms |
3040 KB |
Partially correct |
14 |
Incorrect |
8 ms |
3040 KB |
Output isn't correct |
15 |
Partially correct |
8 ms |
3040 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
2 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
3 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
4 |
Partially correct |
11 ms |
3548 KB |
Partially correct |
5 |
Incorrect |
29 ms |
8148 KB |
Output isn't correct |
6 |
Incorrect |
152 ms |
20152 KB |
Output isn't correct |
7 |
Incorrect |
177 ms |
20484 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
2396 KB |
Partially correct |
2 |
Partially correct |
1 ms |
2528 KB |
Partially correct |
3 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
2 ms |
2392 KB |
Partially correct |
2 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
3 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
2 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
3 |
Partially correct |
2 ms |
2396 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
60 ms |
7124 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
92 ms |
12240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
218 ms |
20412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
243 ms |
20156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |