fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. const double ice_per_year = 252e9;
  6. const double secs_in_year = 365.0 * 24.0 * 60.0 * 60.0;
  7. const double ice_per_sec = ice_per_year / secs_in_year;
  8.  
  9. mt19937_64 rng(42);
  10.  
  11. int main() {
  12.     int n = 1e5;
  13.     long long k = 1e12;
  14.  
  15.     vector<double> a(n);
  16.     for (int i = 0; i < n; ++i) {
  17.         a[i] = rng() % ((long long)1e12) + 1;
  18.     }
  19.     vector<double> c(n, 1);
  20.  
  21.     priority_queue<pair<double, int>> pq;
  22.     for (int i = 0; i < n; ++i) {
  23.         pq.emplace(a[i] / c[i] / (c[i] + 1), i);
  24.     }
  25.  
  26.     cerr << "ice melts per sec in antarctica: " << ice_per_sec << endl;
  27.     auto start_time = clock();
  28.     for (long long i = 0; i < k - n; ++i) {
  29.         int ind = pq.top().second;
  30.         pq.pop();
  31.         c[ind] += 1;
  32.         pq.emplace(a[ind] / c[ind] / (c[ind] + 1), ind);
  33.         if (i % ((int)1e7) == 0) {
  34.             double spent_time = (double)(clock() - start_time) / CLOCKS_PER_SEC;
  35.             double estimated_runtime = spent_time / (i + 1) * (k - n);
  36.             cerr << i << ", spent time: " << spent_time << "s, estimated runtime: " << estimated_runtime << "s";
  37.             cerr << ", estimated ice melts: " << ice_per_sec * estimated_runtime;
  38.             cerr << endl;
  39.         }
  40.     }
  41.  
  42.     double ans = 0;
  43.     for (int i = 0; i < n; ++i) {
  44.         ans += a[i] / c[i];
  45.     }
  46.     cout << (long long)(ans + 0.5) << '\n';
  47.  
  48.     return 0;
  49. }
  50.  
Time limit exceeded #stdin #stdout #stderr 15s 6800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
ice melts per sec in antarctica: 7990.87
0, spent time: 1e-06s, estimated runtime: 1e+06s, estimated ice melts: 7.99087e+09
10000000, spent time: 1.43957s, estimated runtime: 143957s, estimated ice melts: 1.15034e+09
20000000, spent time: 2.87003s, estimated runtime: 143501s, estimated ice melts: 1.1467e+09
30000000, spent time: 4.29899s, estimated runtime: 143300s, estimated ice melts: 1.14509e+09
40000000, spent time: 5.7271s, estimated runtime: 143178s, estimated ice melts: 1.14411e+09
50000000, spent time: 7.17569s, estimated runtime: 143514s, estimated ice melts: 1.1468e+09
60000000, spent time: 8.60978s, estimated runtime: 143496s, estimated ice melts: 1.14666e+09
70000000, spent time: 10.0289s, estimated runtime: 143270s, estimated ice melts: 1.14485e+09
80000000, spent time: 11.4056s, estimated runtime: 142570s, estimated ice melts: 1.13926e+09
90000000, spent time: 12.8349s, estimated runtime: 142610s, estimated ice melts: 1.13957e+09
100000000, spent time: 14.2414s, estimated runtime: 142413s, estimated ice melts: 1.13801e+09
https://ideone.com/c6gFYf
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!