QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116524#4880. Network Transferhos_lyricWA 201ms31180kbC++142.8kb2023-06-29 14:07:442023-06-29 14:07:47

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:07:47]
  • 评测
  • 测评结果:WA
  • 用时:201ms
  • 内存:31180kb
  • [2023-06-29 14:07:44]
  • 提交

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 = long 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("%.10Lf\n", ans[i]);
    }
  }
  return 0;
}

詳細信息

Test #1:

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

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: 3700kb

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: 3676kb

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: 3640kb

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: 3684kb

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: 3628kb

input:

1 10000000
10000000 1 1

output:

10000000.0000001000

result:

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

Test #7:

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

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: 0ms
memory: 3668kb

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: 123ms
memory: 31180kb

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: 177ms
memory: 30412kb

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.3636364937
1390577580645.1612901688
1300784647887.3239434958
1280812465753.4246574640
1190840487804.8780486584
1859583333333.3333334923
1410498166666.6666665077
1750241923076.9230768681
1660420857142.8571428061
1180833975903.6144577265
1430416379310.3448274136
1170834642857.1428570747
...

result:

ok 200000 numbers

Test #11:

score: -100
Wrong Answer
time: 201ms
memory: 30412kb

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.3303611577
212200370284.1514279544
238936116128.1871913522
263414860026.4186147451
197050823829.1730593890
270568706403.5021036118
303455816466.1981295943
237130553749.7986679226
203491960013.6168512255
360160051293.0971049070
364158756929.1208285689
219519740651.8995159417
270174628411...

result:

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