QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51638 | #4880. Network Transfer | zhoukangyang# | WA | 2ms | 3740kb | C++11 | 1.4kb | 2022-10-03 10:03:33 | 2022-10-03 10:03:34 |
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.
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3740kb
input:
2 10 0 100 2 4 200 1
output:
DEC = 2 13 30
result:
wrong output format Expected double, but "DEC" found