QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116523 | #4880. Network Transfer | hos_lyric | WA | 1ms | 3632kb | C++14 | 2.8kb | 2023-06-29 14:07:07 | 2023-06-29 14:07:10 |
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 = 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("%.10f\n", ans[i]);
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3632kb
input:
2 10 0 100 2 4 200 1
output:
0.0000000000 0.0000000000
result:
wrong answer 1st numbers differ - expected: '13.0000000', found: '0.0000000', error = '1.0000000'