제출 #752475

#제출 시각아이디문제언어결과실행 시간메모리
752475wenqiHiring (IOI09_hiring)C++17
100 / 100
343 ms12104 KiB
// trans rights #include <bits/extc++.h> using namespace std; using ll = long long; #ifdef DEBUG #define D(args...) fprintf(stderr, args) #else #define D(...) #endif int N; ll W; struct Node { int cnt; ll sum; }; Node nodes[80005]; void upd(int i, int l, int r, int p) { auto &node = nodes[i]; if (p < l or p > r) return; if (l == r) { node.cnt++; node.sum += p; return; } int m = (l + r) / 2; upd(2 * i, l, m, p); upd(2 * i + 1, m + 1, r, p); node.cnt = nodes[2 * i].cnt + nodes[2 * i + 1].cnt; node.sum = nodes[2 * i].sum + nodes[2 * i + 1].sum; } pair<int, ll> query(int i, int l, int r, int scl, ll bound) { auto &node = nodes[i]; if (l == r) { auto k = min<ll>(node.cnt, bound / scl / l); return {k, k * l * scl}; } int m = (l + r) / 2; auto &ln = nodes[2 * i]; if (ln.sum * scl <= bound) { auto w = query(2 * i + 1, m + 1, r, scl, bound - ln.sum * scl); return {w.first + ln.cnt, w.second + ln.sum * scl}; } return query(2 * i, l, m, scl, bound); } int main(int argc, const char *argv[]) { scanf(" %d %lld", &N, &W); vector<tuple<int, int, int>> p; for (int i = 1; i <= N; i++) { int s, q; scanf(" %d %d", &s, &q); p.push_back({s, q, i}); } sort(p.begin(), p.end(), [](auto &f, auto &s) { auto [a, b, i] = f; auto [x, y, j] = s; return a * y < b * x; }); int ans = 0; pair<ll, ll> frac; int marker = -1; for (auto [s, q, i] : p) { upd(1, 1, 20000, q); auto b = query(1, 1, 20000, s, W * q); if (b.first > ans) { ans = b.first; marker = i; frac = {b.second, q}; } else if (b.first == ans and (__int128_t) b.second * frac.second < (__int128_t)frac.first * q) { marker = i; frac = {b.second, q}; } } printf("%d\n", ans); priority_queue<pair<int, int>> pq; for (auto [s, q, i] : p) { pq.push({q, i}); while ((int)pq.size() > ans) pq.pop(); if (i == marker) { while (pq.size()) { printf("%d\n", pq.top().second); pq.pop(); } return 0; } } return 0; }

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

hiring.cpp: In function 'int main(int, const char**)':
hiring.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf(" %d %lld", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
hiring.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf(" %d %d", &s, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
#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...