QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#51639 | #4880. Network Transfer | zhoukangyang# | WA | 195ms | 13628kb | C++11 | 1.4kb | 2022-10-03 10:03:58 | 2022-10-03 10:04:00 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define ull unsigned long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
using namespace std;
const int N = 1e6 + 7, mod = 998244353;
int n, w, t[N], p[N], ord[N];
double s[N], Dec, allp, ns[N];
priority_queue < pair < double, int > > q;
void dt(double tim, double cur) {
while(sz(q) && (-q.top().first - Dec) * allp <= tim) {
int u = q.top().second;
double t = (-q.top().first - Dec) * allp;
Dec += t / allp;
tim -= t, cur += t, ns[u] = cur, allp -= p[u];
q.pop();
}
if(allp) Dec += tim / allp; //, cout << "DEC = " << Dec << '\n';
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> w;
L(i, 1, n) {
int qwq;
cin >> t[i] >> qwq >> p[i];
s[i] = qwq, s[i] /= w, s[i] /= p[i];
ord[i] = i;
// cout << "si = " << s[i] << endl;
}
sort(ord + 1, ord + n + 1, [&] (int x, int y) {
return t[x] < t[y];
});
int lst = 0;
L(o, 1, n) {
int i = ord[o];
dt(t[i] - lst, lst), lst = t[i];
// cout << "LST = " << lst << endl;
q.push({-(s[i] + Dec), i});
allp += p[i];
}
dt(1e18, lst);
L(i, 1, n) cout << ns[i] << '\n';
return 0;
}
/*
transferred per sec : 1 / allp.
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5804kb
input:
2 10 0 100 2 4 200 1
output:
13 30
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 6000kb
input:
2 10 30 200 1 10 100 2
output:
50 20
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 5720kb
input:
1 10000000 0 1 42
output:
1e-07
result:
ok found '0.0000001', expected '0.0000001', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5816kb
input:
1 10000000 42 1 42
output:
42
result:
ok found '42.0000000', expected '42.0000001', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
1 10000000 42 10000000 42
output:
43
result:
ok found '43.0000000', expected '43.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5996kb
input:
1 10000000 10000000 1 1
output:
1e+07
result:
ok found '10000000.0000000', expected '10000000.0000001', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
1 10000000 1 1 100
output:
1
result:
ok found '1.0000000', expected '1.0000001', error '0.0000001'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5856kb
input:
1 1 10000000 10000000 100
output:
2e+07
result:
ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 144ms
memory: 13628kb
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:
2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 2.00001e+12 ...
result:
ok 200000 numbers
Test #10:
score: -100
Wrong Answer
time: 195ms
memory: 13252kb
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:
1.79004e+12 1.39058e+12 1.30078e+12 1.28081e+12 1.19084e+12 1.85958e+12 1.4105e+12 1.75024e+12 1.66042e+12 1.18083e+12 1.43042e+12 1.17083e+12 1.78007e+12 1.61042e+12 1.25085e+12 1.66042e+12 1.54034e+12 1.50027e+12 1.5704e+12 1.35068e+12 1.5704e+12 1.60042e+12 1.21085e+12 1.48027e+12 1.90977e+12 1.2...
result:
wrong answer 2nd numbers differ - expected: '1390577580645.1613770', found: '1390580000000.0000000', error = '0.0000017'