QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533898#3962. 100 meter dashYarema#AC ✓47ms9656kbC++201.5kb2024-08-26 16:19:242024-08-26 16:19:24

Judging History

This is the latest submission verdict.

  • [2024-08-26 16:19:24]
  • Judged
  • Verdict: AC
  • Time: 47ms
  • Memory: 9656kb
  • [2024-08-26 16:19:24]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;

db dis(db x1, db y1, db x2, db y2)
{
	db dx = x1 - x2;
	db dy = y1 - y2;
	return sqrt(dx * dx + dy * dy);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<db> x(n + 1), y(n + 1), t(n + 1);
	FOR (i, 0, n)
		cin >> x[i + 1] >> y[i + 1] >> t[i + 1];
	vector<db> d(n + 1);
	FOR (i, 0, n)
	{
		d[i + 1] = d[i] + dis(x[i], y[i], x[i + 1], y[i + 1]);
	}
	//FOR (i, 0, n + 1)
	//{
	//	cerr << i << ' ' << d[i] << ' ' << t[i] << '\n';
	//}
	//cerr << "\n\n\n";
	db ans = 1e47;
	int j = 0;
	FOR (i, 0, n + 1)
	{
		while (j < n + 1 && d[j] < d[i] + 100)
			j++;
		if (j == n + 1)
			break;
		db T = t[j - 1] - t[i];
		T += (100 - (d[j - 1] - d[i])) * (t[j] - t[j - 1]) / (d[j] - d[j - 1]);
		ans = min(ans, T);
	}
	j = n;
	RFOR (i, n + 1, 0)
	{
		while (j >= 0 && d[j] + 100 > d[i])
			j--;
		if (j == -1)
			break;
		db T = t[i] - t[j + 1];
		T += (100 - (d[i] - d[j + 1])) * (t[j + 1] - t[j]) / (d[j + 1] - d[j]); 
		ans = min(ans, T);
	}
	
	cout << fixed << setprecision(15) << ans << '\n';
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

2
50 0 10
140 0 20

output:

12.000000000000000

result:

ok found '12.00000', expected '12.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

6
84.39 0 10
120.89 36.5 14.3
84.39 73 18.4
0 73 28.5
-36.5 36.5 32.7
0 0 36.95

output:

8.130299066033300

result:

ok found '8.13030', expected '8.13030', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

5
20 0 1
50 0 6
30 0 8
-40 0 15
40 0 17

output:

4.000000000000000

result:

ok found '4.00000', expected '4.00000', error '0.00000'

Test #4:

score: 0
Accepted
time: 38ms
memory: 8864kb

input:

85860
-18.000000 15.000000 28.000000
-58.000000 -69.000000 39.000000
61.000000 26.000000 54.000000
42.000000 52.000000 67.000000
-8.000000 -83.000000 78.000000
-68.000000 29.000000 97.000000
-14.000000 62.000000 114.000000
86.000000 -15.000000 127.000000
0.000000 34.000000 148.000000
-23.000000 54.0...

output:

4.394448922628262

result:

ok found '4.39445', expected '4.39445', error '0.00000'

Test #5:

score: 0
Accepted
time: 21ms
memory: 5836kb

input:

42118
22.000000 -15.000000 16.000000
71.000000 43.000000 41.000000
85.000000 -84.000000 52.000000
38.000000 -36.000000 82.000000
1.000000 -13.000000 104.000000
-54.000000 -46.000000 121.000000
54.000000 -53.000000 132.000000
-19.000000 -29.000000 145.000000
-12.000000 -2.000000 156.000000
65.000000 ...

output:

4.394063237045975

result:

ok found '4.39406', expected '4.39406', error '0.00000'

Test #6:

score: 0
Accepted
time: 22ms
memory: 6632kb

input:

54051
-41.000000 24.000000 16.000000
43.000000 41.000000 27.000000
-4.000000 -71.000000 42.000000
-35.000000 27.000000 72.000000
-83.000000 50.000000 102.000000
-43.000000 -49.000000 130.000000
7.000000 -1.000000 148.000000
-35.000000 -51.000000 167.000000
91.000000 -91.000000 185.000000
-62.000000 ...

output:

4.292031384129273

result:

ok found '4.29203', expected '4.29203', error '0.00000'

Test #7:

score: 0
Accepted
time: 17ms
memory: 5600kb

input:

34594
-53.000000 -67.000000 11.000000
17.000000 1.000000 35.000000
-73.000000 99.000000 58.000000
6.000000 -89.000000 79.000000
-1.000000 -95.000000 93.000000
-10.000000 -8.000000 117.000000
31.000000 60.000000 145.000000
86.000000 45.000000 164.000000
-87.000000 -85.000000 187.000000
5.000000 -22.0...

output:

4.492378702725284

result:

ok found '4.49238', expected '4.49238', error '0.00000'

Test #8:

score: 0
Accepted
time: 36ms
memory: 8216kb

input:

79822
-25.000000 -98.000000 25.000000
-94.000000 -36.000000 52.000000
-72.000000 -87.000000 65.000000
-31.000000 60.000000 83.000000
90.000000 80.000000 99.000000
-30.000000 -95.000000 111.000000
90.000000 -15.000000 129.000000
-54.000000 2.000000 142.000000
52.000000 -22.000000 159.000000
-79.00000...

output:

4.193070802107418

result:

ok found '4.19307', expected '4.19307', error '0.00000'

Test #9:

score: 0
Accepted
time: 37ms
memory: 8508kb

input:

83557
3.000000 80.000000 19.000000
-38.000000 50.000000 34.000000
-1.000000 66.000000 49.000000
91.000000 -66.000000 73.000000
13.000000 -5.000000 91.000000
-37.000000 52.000000 119.000000
73.000000 -18.000000 140.000000
-84.000000 -95.000000 152.000000
-76.000000 79.000000 177.000000
48.000000 -83....

output:

4.092869195059620

result:

ok found '4.09287', expected '4.09287', error '0.00000'

Test #10:

score: 0
Accepted
time: 15ms
memory: 5688kb

input:

37672
-42.000000 -43.000000 28.000000
-36.000000 -34.000000 49.000000
-81.000000 -23.000000 78.000000
-96.000000 95.000000 101.000000
42.000000 73.000000 117.000000
-16.000000 -93.000000 131.000000
-29.000000 98.000000 160.000000
28.000000 68.000000 188.000000
97.000000 70.000000 210.000000
58.00000...

output:

4.398944380007999

result:

ok found '4.39894', expected '4.39894', error '0.00000'

Test #11:

score: 0
Accepted
time: 13ms
memory: 5076kb

input:

26231
47.000000 -18.000000 18.000000
0.000000 -12.000000 45.000000
13.000000 47.000000 69.000000
99.000000 7.000000 85.000000
-3.000000 62.000000 115.000000
-17.000000 -40.000000 137.000000
-64.000000 4.000000 159.000000
56.000000 51.000000 174.000000
-6.000000 43.000000 199.000000
62.000000 -51.000...

output:

4.391156334277486

result:

ok found '4.39116', expected '4.39116', error '0.00000'

Test #12:

score: 0
Accepted
time: 26ms
memory: 6716kb

input:

53985
-94.000000 11.000000 23.000000
-67.000000 -4.000000 39.000000
-72.000000 -75.000000 59.000000
-53.000000 17.000000 70.000000
-26.000000 -45.000000 96.000000
3.000000 37.000000 109.000000
-93.000000 30.000000 136.000000
61.000000 -47.000000 162.000000
-69.000000 24.000000 183.000000
39.000000 1...

output:

4.231864899764659

result:

ok found '4.23186', expected '4.23186', error '0.00000'

Test #13:

score: 0
Accepted
time: 44ms
memory: 8796kb

input:

89120
29.000000 36.000000 25.000000
-50.000000 -26.000000 37.000000
-85.000000 49.000000 56.000000
-97.000000 -4.000000 80.000000
-80.000000 -78.000000 107.000000
75.000000 -86.000000 123.000000
15.000000 67.000000 147.000000
63.000000 41.000000 170.000000
35.000000 58.000000 196.000000
17.000000 36...

output:

4.295695314026850

result:

ok found '4.29570', expected '4.29570', error '0.00000'

Test #14:

score: 0
Accepted
time: 44ms
memory: 9564kb

input:

100000
0.000000 0.000000 16.000000
0.002000 0.000000 24.000000
0.004000 0.000000 40.000000
0.006000 0.000000 50.000000
0.008000 0.000000 66.000000
0.010000 0.000000 71.000000
0.012000 0.000000 75.000000
0.014000 0.000000 90.000000
0.016000 0.000000 108.000000
0.018000 0.000000 122.000000
0.020000 0....

output:

523123.000000000000000

result:

ok found '523123.00000', expected '523123.00000', error '0.00000'

Test #15:

score: 0
Accepted
time: 39ms
memory: 9616kb

input:

100000
0.000000 0.000000 6.000000
0.002000 0.000000 14.000000
0.004000 0.000000 18.000000
0.006000 0.000000 24.000000
0.008000 0.000000 40.000000
0.010000 0.000000 49.000000
0.012000 0.000000 61.000000
0.014000 0.000000 78.000000
0.016000 0.000000 83.000000
0.018000 0.000000 89.000000
0.020000 0.000...

output:

524768.000000000000000

result:

ok found '524768.00000', expected '524768.00000', error '0.00000'

Test #16:

score: 0
Accepted
time: 47ms
memory: 9584kb

input:

100000
0.000000 0.000000 16.000000
0.002000 0.000000 17.000000
0.004000 0.000000 32.000000
0.006000 0.000000 35.000000
0.008000 0.000000 53.000000
0.010000 0.000000 64.000000
0.012000 0.000000 69.000000
0.014000 0.000000 84.000000
0.016000 0.000000 93.000000
0.018000 0.000000 96.000000
0.020000 0.00...

output:

524231.000000000000000

result:

ok found '524231.00000', expected '524231.00000', error '0.00000'

Test #17:

score: 0
Accepted
time: 44ms
memory: 9508kb

input:

100000
0.000000 0.000000 18.000000
0.002000 0.000000 33.000000
0.004000 0.000000 47.000000
0.006000 0.000000 63.000000
0.008000 0.000000 72.000000
0.010000 0.000000 77.000000
0.012000 0.000000 89.000000
0.014000 0.000000 95.000000
0.016000 0.000000 98.000000
0.018000 0.000000 104.000000
0.020000 0.0...

output:

523877.999999999999972

result:

ok found '523878.00000', expected '523878.00000', error '0.00000'

Test #18:

score: 0
Accepted
time: 43ms
memory: 9588kb

input:

100000
0.000000 0.000000 12.000000
0.002000 0.000000 23.000000
0.004000 0.000000 27.000000
0.006000 0.000000 41.000000
0.008000 0.000000 60.000000
0.010000 0.000000 74.000000
0.012000 0.000000 77.000000
0.014000 0.000000 94.000000
0.016000 0.000000 101.000000
0.018000 0.000000 118.000000
0.020000 0....

output:

522742.999999999999972

result:

ok found '522743.00000', expected '522743.00000', error '0.00000'

Test #19:

score: 0
Accepted
time: 47ms
memory: 9588kb

input:

100000
0.000000 0.000000 6.000000
0.002000 0.000000 12.000000
0.004000 0.000000 15.000000
0.006000 0.000000 26.000000
0.008000 0.000000 45.000000
0.010000 0.000000 63.000000
0.012000 0.000000 73.000000
0.014000 0.000000 93.000000
0.016000 0.000000 111.000000
0.018000 0.000000 114.000000
0.020000 0.0...

output:

522664.000000000000000

result:

ok found '522664.00000', expected '522664.00000', error '0.00000'

Test #20:

score: 0
Accepted
time: 47ms
memory: 9656kb

input:

100000
0.000000 0.000000 8.000000
0.002000 0.000000 10.000000
0.004000 0.000000 23.000000
0.006000 0.000000 37.000000
0.008000 0.000000 49.000000
0.010000 0.000000 57.000000
0.012000 0.000000 68.000000
0.014000 0.000000 87.000000
0.016000 0.000000 105.000000
0.018000 0.000000 118.000000
0.020000 0.0...

output:

524593.999999999999943

result:

ok found '524594.00000', expected '524594.00000', error '0.00000'

Test #21:

score: 0
Accepted
time: 44ms
memory: 9548kb

input:

100000
0.000000 0.000000 19.000000
0.002000 0.000000 39.000000
0.004000 0.000000 57.000000
0.006000 0.000000 63.000000
0.008000 0.000000 68.000000
0.010000 0.000000 88.000000
0.012000 0.000000 89.000000
0.014000 0.000000 109.000000
0.016000 0.000000 123.000000
0.018000 0.000000 126.000000
0.020000 0...

output:

524614.000000000000000

result:

ok found '524614.00000', expected '524614.00000', error '0.00000'

Test #22:

score: 0
Accepted
time: 39ms
memory: 9512kb

input:

100000
0.000000 0.000000 14.000000
0.002000 0.000000 25.000000
0.004000 0.000000 36.000000
0.006000 0.000000 49.000000
0.008000 0.000000 55.000000
0.010000 0.000000 68.000000
0.012000 0.000000 69.000000
0.014000 0.000000 81.000000
0.016000 0.000000 88.000000
0.018000 0.000000 89.000000
0.020000 0.00...

output:

523898.000000000000028

result:

ok found '523898.00000', expected '523898.00000', error '0.00000'

Test #23:

score: 0
Accepted
time: 40ms
memory: 9592kb

input:

100000
0.000000 0.000000 16.000000
0.002000 0.000000 23.000000
0.004000 0.000000 32.000000
0.006000 0.000000 40.000000
0.008000 0.000000 47.000000
0.010000 0.000000 52.000000
0.012000 0.000000 53.000000
0.014000 0.000000 60.000000
0.016000 0.000000 79.000000
0.018000 0.000000 95.000000
0.020000 0.00...

output:

523109.000000000000000

result:

ok found '523109.00000', expected '523109.00000', error '0.00000'