QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51639#4880. Network Transferzhoukangyang#WA 195ms13628kbC++111.4kb2022-10-03 10:03:582022-10-03 10:04:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-03 10:04:00]
  • 评测
  • 测评结果:WA
  • 用时:195ms
  • 内存:13628kb
  • [2022-10-03 10:03:58]
  • 提交

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: 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'