Submission #892695

#TimeUsernameProblemLanguageResultExecution timeMemory
892695MackerHiring (IOI09_hiring)C++17
30 / 100
469 ms43428 KiB
#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; const ld eps = 1e-50; 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; } pair<int, int> walk(ld b, ld m, int i = 1) { if(i >= len){ if(b - st[i].val * m > -eps) return {st[i].cnt, b - st[i].val * m}; else return {0, b}; } if(b - st[i * 2].val * m > -eps){ pair<int, int> r = walk(b - st[i * 2].val * m, m, i * 2 + 1); return {st[i * 2].cnt + r.first, b - st[i * 2].val * m - r.second}; } else return walk(b, m, i * 2); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; ld 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)); pair<int, int> mx = {0, 0}; int mxi; for (int i = 0; i < n; i++) { auto& [x, q] = v[i]; add(q, q); pair<int, int> ret = walk(b, x); if(ret > mx){ mx = ret; mxi = i; } } set<pair<int, int>> s; vector<int> res; for (int i = 0; i <= mxi; i++) { auto& [x, q] = v[i]; s.insert({q, i}); } int j = 0; for (auto &i : s) { if(j >= mx.first) break; res.push_back(i.second); j++; } cout << mx.first << "\n"; for (auto &&i : res) { cout << i + 1 << "\n"; } }

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:69:23: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     for (int i = 0; i <= mxi; i++) {
      |                     ~~^~~~~~
#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...