QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#277876 | #2483. Roof Escape | Sadimk | WA | 1ms | 3792kb | C++14 | 4.0kb | 2023-12-07 05:54:30 | 2023-12-07 05:54:31 |
Judging History
answer
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define vt vector
#define pii pair<int, int>
#define pb push_back
#define umap unordered_map
#define uset unordered_set
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define contains(l, a) l.find(a) != l.end()
#define DEBUG 1
#define dbg(x) \
if (DEBUG) { cout << #x << " = " << x << endl; }
#define dbgv(x) \
if (DEBUG) { \
cout << #x << " = "; \
for (auto _i : x) cout << _i << " "; \
cout << endl; \
}
#define dbgm(x, n, m) \
if (DEBUG) { \
cout << #x << " = " << endl; \
FOR(_i, 0, n) { \
FOR(_j, 0, m) cout << x[_i][_j] << " "; \
cout << endl; \
} \
}
typedef int T;
struct pt {
T x, y;
pt(T x = 0, T y = 0) : x(x), y(y) {}
};
bool segInt(pt p1, pt p2, pt p3, pt p4) {
int d1 = (p4.y - p3.y) * (p1.x - p3.x) + (p3.x - p4.x) * (p1.y - p3.y);
int d2 = (p4.y - p3.y) * (p2.x - p3.x) + (p3.x - p4.x) * (p2.y - p3.y);
int d3 = (p2.y - p1.y) * (p3.x - p1.x) + (p1.x - p2.x) * (p3.y - p1.y);
int d4 = (p2.y - p1.y) * (p4.x - p1.x) + (p1.x - p2.x) * (p4.y - p1.y);
return ((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0));
}
int main() {
cout.precision(10);
int W, H, Sx, Sy, Ex, Ey; cin >> W >> H >> Sx >> Sy >> Ex >> Ey;
ld hor = sqrtl((Sx - Ex)*(Sx - Ex) + (Sy - Ey)*(Sy - Ey));
H /= 2;
W /= 2;
vt<vi> grid(H, vi(W));
FOR(i, 0, H) FOR (j, 0, W) cin >> grid[i][j];
int Dx = abs(Ex-Sx);
int Dy = abs(Ey-Sy);
pt s(Sx, Sy), e(Ex, Ey);
int vert = 0;
int current_height = grid[Sy/2][Sx/2];
int grid_x = Sx/2;
int grid_y = Sy/2;
int grid_dx = (Ex > Sx) - (Sx > Ex);
int grid_dy = (Ey > Sy) - (Sy > Ey);
if (Dx > Dy) {
int dx = (Ex > Sx) - (Sx > Ex);
int dy = 2*((Ey > Sy) - (Sy > Ey));
int y = Sy-dy/2;
for (int x = Sx; x != Ex; x+=dx) {
if (x%2) continue;
bool int1 = segInt(s, e, pt(x, y), pt(x, y+dy));
bool int2 = segInt(s, e, pt(x, y+dy), pt(x, y+2*dy));
int h1 = grid[grid_y][grid_x+grid_dx];
int h2 = grid[grid_y+grid_dy][grid_x+grid_dx];
int h3 = grid[grid_y+grid_dy][grid_x];
if (!int1 && !int2) {
// first move up (to Q)
vi temp = {h1, h2, h3};
sort(all(temp));
if (temp[1] > current_height) {
vert += abs(current_height - temp[1]);
current_height = temp[1];
}
// Now move down
vert += abs(current_height - h2);
current_height = h2;
y += dy;
grid_y += grid_dy;
} else if (int1) {
vert += abs(current_height - h1);
current_height = h1;
} else {
vert += abs(current_height - h3);
current_height = h3;
y += dy;
grid_y += grid_dy;
}
grid_x += grid_dx;
}
} else {
int dy = (Ey > Sy) - (Sy > Ey);
int dx = 2*((Ex > Sx) - (Sx > Ex));
int x = Sx-dx/2;
for (int y = Sy; y != Ey; y+=dy) {
if (y%2) continue;
bool int1 = segInt(s, e, pt(x, y), pt(x+dx, y));
bool int2 = segInt(s, e, pt(x+dx, y), pt(x+2*dx, y));
int h1 = grid[grid_y+grid_dy][grid_x];
int h2 = grid[grid_y+grid_dy][grid_x+grid_dx];
int h3 = grid[grid_y][grid_x+grid_dx];
if (!int1 && !int2) {
// first move up (to Q)
vi temp = {h1, h2, h3};
sort(all(temp));
if (temp[1] > current_height) {
vert += abs(current_height - temp[1]);
current_height = temp[1];
}
// Now move down
vert += abs(current_height - h2);
current_height = h2;
x += dx;
grid_x += grid_dx;
} else if (int1) {
vert += abs(current_height - h1);
current_height = h1;
} else {
vert += abs(current_height - h3);
current_height = h3;
x += dx;
grid_x += grid_dx;
}
grid_y += grid_dy;
}
}
cout << hor + vert << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
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.08318916
result:
ok found '53.08319', expected '53.08319', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
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.48528137
result:
ok found '14.48528', expected '14.48528', error '0.00000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
2 2 1 1 1 1 100
output:
0
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 4 1 1 3 3 100 1 1 100
output:
2.828427125
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
4 4 1 1 3 3 1 100 100 1
output:
200.8284271
result:
ok found '200.82843', expected '200.82843', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4 4 1 3 3 1 1 100 100 1
output:
2.828427125
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3736kb
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
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 28 1 9 1 23 2 1 1 3 2 1 2 0 3 1 1 1 1 3
output:
23
result:
ok found '23.00000', expected '23.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
2 18 1 11 1 13 1 0 2 0 4 0 2 2 4
output:
4
result:
ok found '4.00000', expected '4.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3568kb
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
result:
ok found '560.00000', expected '560.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3624kb
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:
46
result:
ok found '46.00000', expected '46.00000', error '0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2 132 1 41 1 65 3 0 3 3 2 2 5 2 0 2 3 3 2 1 2 4 0 4 5 1 2 1 0 2 2 1 0 6 1 1 5 2 1 0 2 4 2 5 1 6 0 3 1 1 5 1 2 7 2 2 2 1 5 6 0 5 4 0 5 2 1 1 1 4 0 0
output:
49
result:
ok found '49.00000', expected '49.00000', error '0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4 100 3 37 3 53 2 0 1 3 0 4 2 0 0 2 0 1 0 4 4 0 5 5 3 6 1 4 1 1 6 0 1 3 3 5 5 4 3 0 2 0 2 3 0 1 0 3 4 4 5 3 3 0 0 2 4 1 0 3 0 5 1 2 1 4 1 0 2 0 2 0 0 0 0 2 4 1 4 0 1 5 4 0 0 2 1 7 6 2 1 4 0 0 0 6 5 5 2 0 0 3 3 1 2 4
output:
30
result:
ok found '30.00000', expected '30.00000', error '0.00000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 80 1 67 3 57 1 4 0 5 1 3 1 6 0 0 5 0 0 1 1 0 0 6 3 0 4 0 1 0 1 2 1 2 0 0 6 2 2 2 1 3 0 3 3 2 2 2 0 3 1 2 0 2 0 0 6 6 1 4 1 4 0 4 1 7 1 3 6 1 3 3 5 5 1 1 4 3 1 4 3 5 5 1 2 1
output:
25.19803903
result:
ok found '25.19804', expected '25.19804', error '0.00000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
6 66 1 59 1 51 2 1 1 5 2 6 2 3 2 0 2 6 2 3 2 0 4 2 4 1 5 2 0 6 4 2 2 0 0 1 1 2 0 3 4 2 0 2 1 1 1 2 4 0 3 0 1 0 2 6 5 1 0 5 0 2 1 1 3 3 2 5 3 3 1 4 1 7 1 3 2 5 2 0 5 3 4 5 4 3 0 5 2 4 0 6 3 2 4 4 1 2 0 0 6 0 4 4 3
output:
17
result:
ok found '17.00000', expected '17.00000', error '0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
6 56 1 19 5 19 1 5 5 1 1 4 4 2 4 0 0 2 0 1 4 4 2 3 3 1 5 4 4 2 4 4 3 3 0 2 0 1 1 7 2 5 0 3 1 4 1 2 6 0 5 3 1 2 0 6 3 5 2 1 1 2 4 0 1 0 0 0 3 5 1 2 5 2 0 4 5 1 6 5 2 3 2 4 5 6 4 5 7 0
output:
9
result:
ok found '9.00000', expected '9.00000', error '0.00000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
8 50 1 31 3 7 4 3 3 1 1 3 0 1 6 0 1 4 0 0 1 5 1 3 0 3 0 4 0 0 3 3 3 5 2 3 2 1 0 5 1 4 1 5 3 7 1 2 4 3 6 0 3 1 2 5 6 0 4 5 4 2 2 1 1 7 6 2 4 3 2 3 3 0 0 0 2 3 2 0 4 1 0 1 3 3 2 0 2 5 2 6 1 0 3 1 2 1 5 2 4 1 0 2 4 2
output:
52.08318916
result:
ok found '52.08319', expected '52.08319', error '0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
8 44 3 13 7 17 1 4 1 5 2 1 0 4 1 0 5 2 0 0 4 0 1 0 4 2 5 2 2 0 0 1 1 1 1 0 2 4 1 0 3 3 4 0 1 0 0 2 2 4 4 1 1 0 4 7 2 2 4 4 4 5 0 2 0 2 4 2 6 2 4 1 3 0 4 6 2 4 7 3 2 0 6 4 1 0 1 2 5 1 2 2 3 0
output:
7.656854249
result:
ok found '7.65685', expected '7.65685', error '0.00000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
100 100 21 15 63 83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
79.92496481
result:
ok found '79.92496', expected '79.92496', error '0.00000'
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3704kb
input:
300 300 199 221 255 3 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ...
output:
261.0777643
result:
wrong answer 1st numbers differ - expected: '271.07776', found: '261.07776', error = '0.03689'