제출 #970967

#제출 시각아이디문제언어결과실행 시간메모리
970967aZvezdaHiring (IOI09_hiring)C++14
100 / 100
271 ms26600 KiB
#include <bits/stdc++.h> using namespace std; #ifndef LOCAL #define cerr if (false) cerr #endif #define endl "\n" template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } typedef long long ll; const ll mod = 1e9 + 7; //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// const ll MAX_N = 5e5 + 10; std::pair<std::pair<ll, ll>, ll> arr[MAX_N]; ll n, w; signed main() { #ifndef LOCAL ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #endif cin >> n >> w; for (ll i = 0; i < n; i ++) { cin >> arr[i].first.first >> arr[i].first.second; arr[i].second = i; } std::sort(arr, arr + n, [](const auto &x, const auto &y) { if (x.first.first * y.first.second == x.first.second * y.first.first) { return x.first.second < y.first.second; } return x.first.first * y.first.second < x.first.second * y.first.first; }); ll best = 0; long double best2 = 1e18; ll best_ind = -1; { std::priority_queue<std::pair<ll, ll> > pq = {}; ll sum = 0; for (ll i = 0; i < n; i ++) { sum += arr[i].first.second; pq.push({arr[i].first.second, i}); if (i != n - 1 && (arr[i].first.first * arr[i + 1].first.second == arr[i].first.second * arr[i + 1].first.first)) { continue; } while (sum * arr[i].first.first > w * arr[i].first.second) { sum -= pq.top().first; pq.pop(); } long double curr = (long double)sum / arr[i].first.second * (long double)arr[i].first.first; if (pq.size() > best) { best = pq.size(); best_ind = i; best2 = curr; } else if(pq.size() == best) { if (best2 > curr) { best2 = curr; best_ind = i; } } } } { std::priority_queue<std::pair<ll, ll> > pq = {}; ll sum = 0; for (ll i = 0; i <= best_ind; i ++) { sum += arr[i].first.second; pq.push({arr[i].first.second, arr[i].second}); } while (sum * arr[best_ind].first.first > w * arr[best_ind].first.second) { sum -= pq.top().first; pq.pop(); } std::cout << pq.size() << endl; std::vector<ll> ret = {}; while(!pq.empty()) { ret.push_back(pq.top().second + 1); pq.pop(); } std::sort(ret.begin(), ret.end()); for (const auto it : ret) { std::cout << it << endl; } } return 0; }

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

hiring.cpp: In function 'int main()':
hiring.cpp:55:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   55 |    if (pq.size() > best) {
      |        ~~~~~~~~~~^~~~~~
hiring.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   59 |    } else if(pq.size() == best) {
      |              ~~~~~~~~~~^~~~~~~
#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...