QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203574 | #2483. Roof Escape | Vengeful_Spirit | WA | 1ms | 3800kb | C++14 | 2.1kb | 2023-10-06 18:18:49 | 2023-10-06 18:18:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int W, H;
int a[100006];
int ID(int i, int j) {
return (i-1)*H/2+j;
}
bool chk(int x, int y, int xi, int yi, int xj, int yj) {
long long v1 = 1ll*x*yi-1ll*y*xi;
long long v2 = 1ll*x*yj-1ll*y*xj;
return (v1>0&&v2<0)||(v1<0&&v2>0);
}
bool check(int x, int y, int xx, int yy, int u, int v, int uu, int vv) {
return chk(xx-x, yy-y, u-x, v-y, uu-x, vv-y) && chk(uu-u, vv-v, x-u, y-v, xx-u, yy-v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> W >> H;
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
double ans = sqrt(1ll*(sx-ex)*(sx-ex)+1ll*(sy-ey)*(sy-ey));
vector<tuple<int,int,int>> s;
for(int i = 1; i <= H/2; ++i) {
for(int j = 1; j <= W/2; ++j) {
cin >> a[ID(j, i)];
// if(j == 2 && i == 3) {
// cerr << sx << " " << sy << " " << ex << " " << ey << "\n";
// cerr << 2*j-2 << " " << 2*i-2 << " " << 2*j << " " << 2*i << "\n";
// }
// cout << check(1, 7, 7, 1, 2, 4, 4, 6) << "\n";
if(check(sx, sy, ex, ey, 2*j-2, 2*i-2, 2*j, 2*i)
|| check(sx, sy, ex, ey, 2*j, 2*i-2, 2*j-2, 2*i)
|| (j == (sx+1)/2 && i == (sy+1)/2)
|| (j == (ex+1)/2 && i == (ey+1)/2)) {
// cerr << j << " " << i << "\n";
s.push_back({abs(j*2-sx)+abs(i*2-sy), j, i});
}
}
}
sort(s.begin(), s.end());
for(int i = 0; i < s.size()-1; ++i) {
auto [w, x, y] = s[i];
auto [ww, xx, yy] = s[i+1];
// cerr << x << " " << y << " " << xx << " " << yy << "\n";
if(x==xx||y==yy) ans += abs(a[ID(xx, yy)]-a[ID(x, y)]);
else {
int h1 = a[ID(xx, yy)], h2 = a[ID(x, y)];
int h3 = min(a[ID(x, yy)], a[ID(xx, y)]);
// cerr << h1 << " " << h2 << " " << h3 << "\n";
if(h3 > h1 && h3 > h2) ans += abs(h3-h2)+abs(h3-h1);
else ans += abs(h2-h1);
}
}
cout << fixed << setprecision(10) << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
4 26 1 1 3 25 0 1 0 5 5 5 0 1 2 1 4 1 5 0 0 0 1 0 6 4 3 2 5 4 1 5
output:
53.0831891576
result:
ok found '53.08319', expected '53.08319', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
8 8 1 7 7 1 2 3 2 0 2 1 1 2 1 2 0 0 0 0 0 1
output:
14.4852813742
result:
ok found '14.48528', expected '14.48528', error '0.00000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
2 2 1 1 1 1 100
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
4 4 1 1 3 3 100 1 1 100
output:
2.8284271247
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
4 4 1 1 3 3 1 100 100 1
output:
200.8284271247
result:
ok found '200.82843', expected '200.82843', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
4 4 1 3 3 1 1 100 100 1
output:
2.8284271247
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
2 56 1 23 1 17 1 0 1 0 1 0 0 4 1 3 1 1 3 0 3 1 1 0 0 2 0 2 1 0 1 0 0 0
output:
10.0000000000
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
2 28 1 9 1 23 2 1 1 3 2 1 2 0 3 1 1 1 1 3
output:
23.0000000000
result:
ok found '23.00000', expected '23.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
2 18 1 11 1 13 1 0 2 0 4 0 2 2 4
output:
4.0000000000
result:
ok found '4.00000', expected '4.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
2 400 1 133 1 399 3 6 2 3 0 2 0 3 6 1 6 3 1 5 3 1 6 3 0 2 4 3 3 2 3 0 6 4 2 5 0 3 1 1 3 0 1 3 0 3 5 2 1 2 4 5 0 2 1 0 4 7 3 1 6 4 3 5 2 0 0 3 2 0 2 7 1 0 2 1 2 0 3 0 3 0 6 2 0 4 2 0 3 3 5 0 3 6 3 0 3 2 1 5 1 1 2 6 1 2 1 0 1 2 1 3 2 4 0 5 1 4 2 2 4 4 3 2 1 5 2 3 1 0 0 2 7 5 0 0 2 1 1 0 4 4 2 0 1 4 5 ...
output:
560.0000000000
result:
ok found '560.00000', expected '560.00000', error '0.00000'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3800kb
input:
2 200 1 117 1 97 1 7 2 2 0 4 3 0 0 0 0 5 4 0 4 4 7 0 2 7 3 5 0 1 2 4 2 0 0 0 3 3 1 3 2 2 2 0 3 3 3 0 0 3 1 3 4 2 1 6 0 1 0 2 1 3 5 2 5 2 0 1 0 1 0 1 1 3 3 3 1 5 1 1 7 0 2 2 2 7 2 1 4 3 1 1 0 0 1 2 1 0 6 2 2 2 1 1 1 0
output:
43.0000000000
result:
wrong answer 1st numbers differ - expected: '46.00000', found: '43.00000', error = '0.06522'