QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#277877	#2483. Roof Escape	Sadimk	WA	1ms	3876kb	C++14	4.0kb	2023-12-07 05:56:58	2023-12-07 05:56:58

Judging History

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

[2023-12-07 05:56:58]
评测

测评结果：WA
用时：1ms
内存：3876kb

查看

[2023-12-07 05:56:58]
提交

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[2] > 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[2] > 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;



}

源文件, 语言: C++14

详细

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: 3652kb

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: 3720kb

input:

2 2 1 1 1 1
100

output:

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3620kb

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: 3708kb

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: 1ms

memory: 3728kb

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: 0ms

memory: 3608kb

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:

result:

ok found '10.00000', expected '10.00000', error '0.00000'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

2 28 1 9 1 23
2
1
1
3
2
1
2
0
3
1
1
1
1
3

output:

result:

ok found '23.00000', expected '23.00000', error '0.00000'

Test #9:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

2 18 1 11 1 13
1
0
2
0
4
0
2
2
4

output:

result:

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

Test #10:

score: 0

Accepted

time: 0ms

memory: 3800kb

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:

result:

ok found '560.00000', expected '560.00000', error '0.00000'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3660kb

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:

result:

ok found '46.00000', expected '46.00000', error '0.00000'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3716kb

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:

result:

ok found '49.00000', expected '49.00000', error '0.00000'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3656kb

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:

result:

ok found '30.00000', expected '30.00000', error '0.00000'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3624kb

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: 3680kb

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:

result:

ok found '17.00000', expected '17.00000', error '0.00000'

Test #16:

score: 0

Accepted

time: 1ms

memory: 3732kb

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:

result:

ok found '9.00000', expected '9.00000', error '0.00000'

Test #17:

score: 0

Accepted

time: 1ms

memory: 3732kb

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: 1ms

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: 3564kb

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: 3876kb

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'