QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116522 | #4880. Network Transfer | hos_lyric | WA | 155ms | 18096kb | C++14 | 2.8kb | 2023-06-29 14:06:37 | 2023-06-29 14:06:38 |
Judging History
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;
}
详细
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'