Submission #997374

#TimeUsernameProblemLanguageResultExecution timeMemory
997374GhettoHiring (IOI09_hiring)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ldouble = long double; using pli = pair<ldouble, int>; const int MAX_N = 5e5 + 5, MAX_S = 2e4 + 5; int n; ldouble m; ldouble p[MAX_N], s[MAX_N]; pli a[MAX_N]; struct Node { int count; ldouble sum; bool is_worse(Node other) { if (count == other.count) return sum > other.sum; return count < other.count; } Node operator+(Node other) { return {count + other.count, sum + other.sum}; }; }; Node st[4 * MAX_S]; void update(int i, int u = 1, int lo = 1, int hi = MAX_S) { if (i < lo || hi < i) return; if (lo == hi) { st[u] = {st[u].count + 1, st[u].sum + i}; return; }; int mid = (lo + hi) / 2; update(i, 2 * u, lo, mid), update(i, 2 * u + 1, mid + 1, hi); st[u] = st[2 * u] + st[2 * u + 1]; } Node query(int l, int r, int u = 1, int lo = 1, int hi = MAX_S) { if (r < lo || hi < l) return {0, 0}; if (l <= lo && hi <= r) return st[u]; int mid = (lo + hi) / 2; return query(l, r, 2 * u, lo, mid) + query(l, r, 2 * u + 1, mid + 1, hi); } int walk(ldouble x, int u = 1, int lo = 1, int hi = MAX_S) { if (lo == hi && st[u].sum > x) return -1; if (lo == hi) return lo; int mid = (lo + hi) / 2; if (st[2 * u].sum > x) return walk(x, 2 * u, lo, mid); int ans = walk(x - st[2 * u].sum, 2 * u + 1, mid + 1, hi); if (ans == -1) return walk(x, 2 * u, lo, mid); return ans; } int main() { freopen("hiring.in", "r", stdin), freopen("hiring.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> p[i] >> s[i]; a[i] = {p[i] / s[i], i}; } sort(a + 1, a + n + 1); Node ans = {0, 0}; int opt = -1; for (int j = 1; j <= n; j++) { int i = a[j].second; update(s[i]); ldouble tar = m / a[j].first; int ind = walk(tar); if (ind == -1) continue; Node new_ans = {query(1, ind).count, query(1, ind).sum * a[j].first}; if (new_ans.is_worse(ans)) continue; ans = new_ans, opt = j; } if (opt == -1) { cout << 0 << '\n'; exit(0); } vector<int> list; set<pli> ord; for (int j = 1; j <= n; j++) { int i = a[j].second; ord.insert({s[i], i}); if (j != opt) continue; ldouble tar = m / a[j].first; ldouble sum = 0; for (auto it = ord.begin(); it != ord.end(); it++) { if (sum + it->first > tar) break; sum += it->first; list.push_back(it->second); } break; } assert(ans.count == (int) list.size()); cout << list.size() << '\n'; for (int x : list) cout << x << '\n'; }

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("hiring.in", "r", stdin), freopen("hiring.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:46:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("hiring.in", "r", stdin), freopen("hiring.out", "w", stdout);
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...