QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116522#4880. Network Transferhos_lyricWA 155ms18096kbC++142.8kb2023-06-29 14:06:372023-06-29 14:06:38

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 14:06:38]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:18096kb
  • [2023-06-29 14:06:37]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


using Double = double;
constexpr Double INF = 1e+20;

int N;
Double W;
vector<Double> T, S, P;

int main() {
  for (; ~scanf("%d", &N); ) {
    {
      int w;
      scanf("%d", &w);
      W = w;
    }
    T.resize(N);
    S.resize(N);
    P.resize(N);
    for (int i = 0; i < N; ++i) {
      int t, s, p;
      scanf("%d%d%d", &t, &s, &p);
      T[i] = t;
      S[i] = s;
      P[i] = p;
    }
    
    for (int i = 0; i < N; ++i) {
      S[i] /= W;
    }
#define W do_not_use_W
    
    vector<pair<Double, int>> adds(N + 1);
    for (int i = 0; i < N; ++i) {
      adds[i] = make_pair(T[i], i);
    }
    adds[N] = make_pair(INF, -1);
    sort(adds.begin(), adds.end());
    
    using Entry = pair<Double, int>;
    priority_queue<Entry, vector<Entry>, greater<Entry>> que;
    
    vector<Double> ans(N, -1.0);
    Double t = 0.0, p = 0.0;
    Double sent = 0.0;
    for (const auto &ti : adds) {
      const Double tt = ti.first;
      for (; !que.empty(); ) {
        const Double s = que.top().first;
        const int i = que.top().second;
        const Double tDone = t + (s - sent) * p;
        if (tDone <= tt) {
          ans[i] = tDone;
          if (p) sent += (tDone - t) / p;
          t = tDone;
          p -= P[i];
          que.pop();
        } else {
          break;
        }
      }
      {
        const int i = ti.second;
        if (~i) {
          if (p) sent += (tt - t) / p;
          t = tt;
          p += P[i];
          que.emplace((sent + S[i]) / P[i], i);
        }
      }
    }
    
    for (int i = 0; i < N; ++i) {
      printf("%.10f\n", ans[i]);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

2 10
0 100 2
4 200 1

output:

13.0000000000
30.0000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

2 10
30 200 1
10 100 2

output:

50.0000000000
20.0000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1 10000000
0 1 42

output:

0.0000001000

result:

ok found '0.0000001', expected '0.0000001', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1 10000000
42 1 42

output:

42.0000001000

result:

ok found '42.0000001', expected '42.0000001', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

1 10000000
42 10000000 42

output:

43.0000000000

result:

ok found '43.0000000', expected '43.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

1 10000000
10000000 1 1

output:

10000000.0000001006

result:

ok found '10000000.0000001', expected '10000000.0000001', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

1 10000000
1 1 100

output:

1.0000001000

result:

ok found '1.0000001', expected '1.0000001', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

1 1
10000000 10000000 100

output:

20000000.0000000000

result:

ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 121ms
memory: 16944kb

input:

200000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10...

output:

2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
2000010000000.0000000000
...

result:

ok 200000 numbers

Test #10:

score: 0
Accepted
time: 152ms
memory: 17208kb

input:

200000 1
10000000 10000000 22
10000000 10000000 62
10000000 10000000 71
10000000 10000000 73
10000000 10000000 82
10000000 10000000 15
10000000 10000000 60
10000000 10000000 26
10000000 10000000 35
10000000 10000000 83
10000000 10000000 58
10000000 10000000 84
10000000 10000000 23
10000000 10000000 ...

output:

1790041363636.3642578125
1390577580645.1613769531
1300784647887.3242187500
1280812465753.4250488281
1190840487804.8784179688
1859583333333.3339843750
1410498166666.6667480469
1750241923076.9238281250
1660420857142.8579101562
1180833975903.6147460938
1430416379310.3449707031
1170834642857.1430664062
...

result:

ok 200000 numbers

Test #11:

score: -100
Wrong Answer
time: 155ms
memory: 18096kb

input:

199293 5
9504657 9159218 4
9229606 9939393 93
9949326 9400061 74
9049202 9678955 63
9856746 9805686 100
9900514 9492706 58
9077984 9828311 42
9082259 9783365 78
9815702 9654015 95
9655893 9753916 11
9027905 9930425 9
9210664 9496857 85
9488366 9132506 56
9416678 9238290 2
9475297 9343399 28
9442121 ...

output:

372595430930.3391723633
212200370284.1518859863
238936116128.1880798340
263414860026.4210815430
197050823829.1737060547
270568706403.5048522949
303455816466.2001953125
237130553749.7994079590
203491960013.6183166504
360160051293.1029052734
364158756929.1279907227
219519740651.8996276855
270174628411...

result:

wrong answer 1st numbers differ - expected: '372606864555.1232910', found: '372595430930.3391724', error = '0.0000307'