QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#558558 | #3962. 100 meter dash | LaVuna47 | AC ✓ | 44ms | 4844kb | C++17 | 3.1kb | 2024-09-11 16:46:16 | 2024-09-11 16:46:16 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define RFOR(i, n) for(int i = n-1; i >= 0; --i)
#define output_vec(vec) { FOR(i_, sz(vec)) cout << vec[i_] << ' '; cout << '\n'; }
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<bool> vb;
typedef short si;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
double my_dist(pdd p1, pdd p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
struct Point
{
double x, y;
double t;
};
double get_ans(const vector<double>& dist, const vector<double>& dt, int n)
{
int l = 0;
int r = 0;
double best_t = 1e47;
double cur_t = 0;
double cur_dist = 0;
while(true)
{
while(r < n && cur_dist + dist[r] < 100)
{
cur_dist += dist[r];
cur_t += dt[r];
++r;
}
if(r == n)
break;
assert(cur_dist < 100 && cur_dist + dist[r] >= 100);
double sp = dist[r]/dt[r];
best_t = min(cur_t + (100-cur_dist)/sp, best_t);
if(r-l > 5)
{
cur_t -= dt[l];
cur_dist -= dist[l];
l += 1;
}
else
{
++l;
r = l;
cur_t = 0;
cur_dist = 0;
}
}
return best_t;
}
int solve()
{
int n;
if(!(cin >> n))
return 1;
vector<double> dist(n,0), dt(n,0);
pdd pr_pos = {0, 0};
double pr_time = 0;
FOR(i, n)
{
pdd cur_pos;
double cur_time;
cin >> cur_pos.x >> cur_pos.y >> cur_time;
dist[i] = my_dist(cur_pos, pr_pos);
dt[i] = cur_time-pr_time;
pr_pos = cur_pos;
pr_time = cur_time;
}
double ans = get_ans(dist, dt, n);
reverse(all(dist));
reverse(all(dt));
ans = min(ans, get_ans(dist, dt, n));
cout << fixed << setprecision(8) << ans << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
2 50 0 10 140 0 20
output:
12.00000000
result:
ok found '12.00000', expected '12.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
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.13029907
result:
ok found '8.13030', expected '8.13030', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5 20 0 1 50 0 6 30 0 8 -40 0 15 40 0 17
output:
4.00000000
result:
ok found '4.00000', expected '4.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 33ms
memory: 4392kb
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.39444892
result:
ok found '4.39445', expected '4.39445', error '0.00000'
Test #5:
score: 0
Accepted
time: 18ms
memory: 3964kb
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.39406324
result:
ok found '4.39406', expected '4.39406', error '0.00000'
Test #6:
score: 0
Accepted
time: 23ms
memory: 4356kb
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.29203138
result:
ok found '4.29203', expected '4.29203', error '0.00000'
Test #7:
score: 0
Accepted
time: 15ms
memory: 3860kb
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.49237870
result:
ok found '4.49238', expected '4.49238', error '0.00000'
Test #8:
score: 0
Accepted
time: 31ms
memory: 4432kb
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.19307080
result:
ok found '4.19307', expected '4.19307', error '0.00000'
Test #9:
score: 0
Accepted
time: 36ms
memory: 4580kb
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.09286920
result:
ok found '4.09287', expected '4.09287', error '0.00000'
Test #10:
score: 0
Accepted
time: 16ms
memory: 4016kb
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.39894438
result:
ok found '4.39894', expected '4.39894', error '0.00000'
Test #11:
score: 0
Accepted
time: 8ms
memory: 4016kb
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.39115633
result:
ok found '4.39116', expected '4.39116', error '0.00000'
Test #12:
score: 0
Accepted
time: 23ms
memory: 4360kb
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.23186490
result:
ok found '4.23186', expected '4.23186', error '0.00000'
Test #13:
score: 0
Accepted
time: 38ms
memory: 4640kb
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.29569531
result:
ok found '4.29570', expected '4.29570', error '0.00000'
Test #14:
score: 0
Accepted
time: 44ms
memory: 4684kb
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:
523122.99999987
result:
ok found '523123.00000', expected '523123.00000', error '0.00000'
Test #15:
score: 0
Accepted
time: 44ms
memory: 4752kb
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:
524767.99999985
result:
ok found '524768.00000', expected '524768.00000', error '0.00000'
Test #16:
score: 0
Accepted
time: 44ms
memory: 4844kb
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:
524230.99999999
result:
ok found '524231.00000', expected '524231.00000', error '0.00000'
Test #17:
score: 0
Accepted
time: 44ms
memory: 4732kb
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.99999997
result:
ok found '523878.00000', expected '523878.00000', error '0.00000'
Test #18:
score: 0
Accepted
time: 42ms
memory: 4780kb
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.99999993
result:
ok found '522743.00000', expected '522743.00000', error '0.00000'
Test #19:
score: 0
Accepted
time: 44ms
memory: 4844kb
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:
522663.99999990
result:
ok found '522664.00000', expected '522664.00000', error '0.00000'
Test #20:
score: 0
Accepted
time: 44ms
memory: 4672kb
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.99999966
result:
ok found '524594.00000', expected '524594.00000', error '0.00000'
Test #21:
score: 0
Accepted
time: 44ms
memory: 4780kb
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:
524613.99999999
result:
ok found '524614.00000', expected '524614.00000', error '0.00000'
Test #22:
score: 0
Accepted
time: 40ms
memory: 4736kb
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:
523897.99999983
result:
ok found '523898.00000', expected '523898.00000', error '0.00000'
Test #23:
score: 0
Accepted
time: 44ms
memory: 4716kb
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.00000000
result:
ok found '523109.00000', expected '523109.00000', error '0.00000'