QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68082#3583. Cyclists versus CloudsYunanAC ✓320ms69760kbC++173.9kb2022-12-14 16:16:252022-12-14 16:16:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-14 16:16:26]
  • 评测
  • 测评结果:AC
  • 用时:320ms
  • 内存:69760kb
  • [2022-12-14 16:16:25]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#define int long long int
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define x first
#define y second
#define MAXN 1005
#define mod 998244353

struct poly
{
  char c;
  int dx, dy, sz;
  pi v[101];
  void read()
  {
    cin >> c >> sz;
    for (int i = 0; i < sz; i++)
    {
      cin >> v[i].x >> v[i].y;
      v[i].x *= 3;
      v[i].y *= 3;
    }
    get_dir();
  }
  void get_dir()
  {
    dx = 0, dy = 0;
    if (c == 'N')
      dy++;
    else if (c == 'S')
      dy--;
    else if (c == 'E')
      dx++;
    else
      dx--;
  }
  vector<pi> translate(int x)
  {
    vector<pi> ans;
    for (auto const &i : v)
      ans.pb({i.x + (x * dx), i.y + (x * dy)});
    return ans;
  }
};

int n;
poly v[101];
bool vis[301][301][310];
bool dp[301][301][310];
bool can[301][301][310];
bool can0[301][301][101];
int mat[301][301];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool is(int x, int y)
{
  return (x >= 0 && x <= 300 && y >= 0 && y <= 300);
}
void dfs(int x, int y)
{
  mat[x][y] = 2;
  for (int d = 0; d < 4; d++)
  {
    int i = x + dx[d], j = y + dy[d];
    if (!is(i, j) || mat[i][j] != 0)
      continue;
    dfs(i, j);
  }
}
bool get(int i, int j, int k)
{
  if (dp[i][j][k])
    return can[i][j][k];
  dp[i][j][k] = 1;
  can[i][j][k] = 1;
  for (int id = 0; id < n; id++)
  {
    int x = i - (k * v[id].dx), y = j - (k * v[id].dy);
    if (is(x, y) && !can0[x][y][id])
      return can[i][j][k] = 0;
  }
  return 1;
}
signed main()
{
  int a, b, c, d;
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> a >> b >> c >> d >> n;
  a *= 3, b *= 3, c *= 3, d *= 3;
  for (int i = 0; i < n; i++)
    v[i].read();
  for (int k = 0; k < n; k++)
  {
    memset(mat, 0, sizeof(mat));
    pi to_fill = {-1, -1};
    for (int i = 0; i < v[k].sz; i++)
    {
      int j = (i + 1) % v[k].sz;
      if (v[k].v[i].x == v[k].v[j].x)
      {
        int a = min(v[k].v[i].y, v[k].v[j].y);
        int b = max(v[k].v[i].y, v[k].v[j].y);
        for (int _ = a; _ <= b; _++)
          mat[v[k].v[i].x][_] = 1;
        pi curr = {v[k].v[i].x - 1, (a + b) >> 1};
        to_fill = max(to_fill, curr);
      }
      else
      {
        int a = min(v[k].v[i].x, v[k].v[j].x);
        int b = max(v[k].v[i].x, v[k].v[j].x);
        for (int _ = a; _ <= b; _++)
          mat[_][v[k].v[i].y] = 1;
      }
    }
    dfs(to_fill.x, to_fill.y);
    for (int i = 0; i <= 300; i++)
    {
      for (int j = 0; j <= 300; j++)
        can0[i][j][k] = (mat[i][j] == 2) ? 0 : 1;
    }
  }
  queue<pii> q;
  q.push({0, {a, b}});
  while (!q.empty())
  {
    int x = q.front().y.x;
    int y = q.front().y.y;
    int t = q.front().x;
    q.pop();
    if (vis[x][y][t])
      continue;
    vis[x][y][t] = 1;
    if (t + 3 <= 309)
    {
      for (int d = 0; d < 4; d++)
      {
        int i = x + dx[d], j = y + dy[d];
        int i2 = x + (2 * dx[d]), j2 = y + (2 * dy[d]);
        int i3 = x + (3 * dx[d]), j3 = y + (3 * dy[d]);
        if (!is(i3, j3))
          continue;
        if (get(i, j, t + 1) && get(i2, j2, t + 2) && get(i3, j3, t + 3))
          q.push({t + 3, {i3, j3}});
      }
      q.push({t + 3, {x, y}}); // parado
    }
  }
  int ans = 1e9;
  for (int i = 0; i <= 309; i++)
  {
    if (vis[c][d][i])
    {
      ans = i / 3;
      break;
    }
  }
  for (int i = 0; i <= 300; i++)
  {
    for (int j = 0; j <= 300; j++)
    {
      if (vis[i][j][309])
      {
        int t = (abs(i - c) / 3) + (abs(j - d) / 3) + 103;
        ans = min(ans, t);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 50ms
memory: 59152kb

input:

4 0 1 4
1
E 8
0 5
3 5
3 2
5 2
5 1
2 1
2 2
0 2

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 65ms
memory: 66600kb

input:

50 0 50 100
2
S 4
0 20
50 20
50 80
0 80
S 4
100 20
50 20
50 80
100 80

output:

100

result:

ok single line: '100'

Test #3:

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

input:

50 0 50 100
3
S 4
0 20
50 20
50 80
0 80
S 4
100 20
50 20
50 80
100 80
S 4
49 80
51 80
51 100
49 100

output:

120

result:

ok single line: '120'

Test #4:

score: 0
Accepted
time: 35ms
memory: 56896kb

input:

1 1 1 1
1
S 4
0 0
0 2
2 2
2 0

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 79ms
memory: 65140kb

input:

29 1 29 25
1
S 8
0 40
29 40
29 20
31 20
31 3
29 3
29 0
0 0

output:

28

result:

ok single line: '28'

Test #6:

score: 0
Accepted
time: 55ms
memory: 60060kb

input:

29 1 29 25
1
S 8
0 40
29 40
29 20
31 20
31 2
29 2
29 0
0 0

output:

43

result:

ok single line: '43'

Test #7:

score: 0
Accepted
time: 51ms
memory: 55932kb

input:

0 0 0 100
1
W 100
0 0
1 0
1 1
2 1
2 2
3 2
3 3
4 3
4 4
5 4
5 5
6 5
6 6
7 6
7 7
8 7
8 8
9 8
9 9
10 9
10 10
11 10
11 11
12 11
12 12
13 12
13 13
14 13
14 14
15 14
15 15
16 15
16 16
17 16
17 17
18 17
18 18
19 18
19 19
20 19
20 20
21 20
21 21
22 21
22 22
23 22
23 23
24 23
24 24
25 24
25 25
26 25
26 26
27 ...

output:

101

result:

ok single line: '101'

Test #8:

score: 0
Accepted
time: 45ms
memory: 56468kb

input:

0 0 0 100
1
W 100
0 0
2 0
2 1
4 1
4 2
6 2
6 3
8 3
8 4
10 4
10 5
12 5
12 6
14 6
14 7
16 7
16 8
18 8
18 9
20 9
20 10
22 10
22 11
24 11
24 12
26 12
26 13
28 13
28 14
30 14
30 15
32 15
32 16
34 16
34 17
36 17
36 18
38 18
38 19
40 19
40 20
42 20
42 21
44 21
44 22
46 22
46 23
48 23
48 24
50 24
50 25
52 25...

output:

150

result:

ok single line: '150'

Test #9:

score: 0
Accepted
time: 48ms
memory: 53156kb

input:

0 0 0 100
1
W 70
0 0
3 0
3 1
6 1
6 2
9 2
9 3
12 3
12 4
15 4
15 5
18 5
18 6
21 6
21 7
24 7
24 8
27 8
27 9
30 9
30 10
33 10
33 11
36 11
36 12
39 12
39 13
42 13
42 14
45 14
45 15
48 15
48 16
51 16
51 17
54 17
54 18
57 18
57 19
60 19
60 20
63 20
63 21
66 21
66 22
69 22
69 23
72 23
72 24
75 24
75 25
78 2...

output:

167

result:

ok single line: '167'

Test #10:

score: 0
Accepted
time: 46ms
memory: 55756kb

input:

0 0 0 100
1
W 100
0 0
1 0
1 1
4 1
4 2
5 2
5 3
8 3
8 4
9 4
9 5
12 5
12 6
14 6
14 7
15 7
15 8
18 8
18 9
19 9
19 10
20 10
20 11
22 11
22 12
25 12
25 13
27 13
27 14
28 14
28 15
31 15
31 16
33 16
33 17
34 17
34 18
37 18
37 19
38 19
38 20
40 20
40 21
42 21
42 22
45 22
45 23
48 23
48 24
51 24
51 25
53 25
5...

output:

145

result:

ok single line: '145'

Test #11:

score: 0
Accepted
time: 139ms
memory: 60160kb

input:

1 50 100 50
20
S 22
31 32
31 39
35 39
35 35
44 35
44 33
45 33
45 38
46 38
46 40
52 40
52 34
53 34
53 31
50 31
50 32
49 32
49 31
47 31
47 30
34 30
34 32
N 18
19 17
19 25
21 25
21 32
23 32
23 25
33 25
33 16
32 16
32 13
36 13
36 9
32 9
32 8
27 8
27 12
24 12
24 17
S 18
20 63
20 69
33 69
33 63
39 63
39 5...

output:

115

result:

ok single line: '115'

Test #12:

score: 0
Accepted
time: 51ms
memory: 57992kb

input:

4 0 1 4
1
S 8
0 5
3 5
3 2
5 2
5 1
2 1
2 2
0 2

output:

8

result:

ok single line: '8'

Test #13:

score: 0
Accepted
time: 60ms
memory: 46564kb

input:

1 50 100 50
20
W 38
57 34
57 39
58 39
58 41
65 41
65 45
67 45
67 41
68 41
68 43
69 43
69 50
66 50
66 49
62 49
62 54
71 54
71 55
72 55
72 56
82 56
82 39
93 39
93 37
92 37
92 23
79 23
79 37
73 37
73 25
66 25
66 26
61 26
61 34
60 34
60 31
58 31
58 34
W 32
64 81
64 91
71 91
71 93
72 93
72 95
73 95
73 96...

output:

150

result:

ok single line: '150'

Test #14:

score: 0
Accepted
time: 135ms
memory: 61908kb

input:

1 50 100 50
20
W 10
26 39
26 55
43 55
43 50
40 50
40 47
43 47
43 34
33 34
33 39
E 10
24 31
24 38
26 38
26 49
32 49
32 43
43 43
43 33
34 33
34 31
E 16
43 33
43 39
49 39
49 49
61 49
61 40
69 40
69 41
79 41
79 35
75 35
75 34
61 34
61 27
52 27
52 33
N 18
65 2
65 13
67 13
67 20
80 20
80 25
73 25
73 35
81...

output:

125

result:

ok single line: '125'

Test #15:

score: 0
Accepted
time: 138ms
memory: 55256kb

input:

1 50 100 50
50
W 18
14 36
14 40
22 40
22 43
28 43
28 41
38 41
38 39
30 39
30 38
39 38
39 28
35 28
35 26
25 26
25 31
21 31
21 36
W 18
50 64
50 67
53 67
53 71
63 71
63 78
73 78
73 67
68 67
68 61
67 61
67 56
60 56
60 60
57 60
57 55
53 55
53 64
S 18
76 42
76 54
83 54
83 53
85 53
85 61
87 61
87 55
91 55
...

output:

138

result:

ok single line: '138'

Test #16:

score: 0
Accepted
time: 56ms
memory: 22872kb

input:

34 99 74 48
100
S 76
0 0
0 66
7 66
7 9
9 9
9 49
13 49
13 34
15 34
15 42
17 42
17 98
26 98
26 73
29 73
29 24
30 24
30 34
31 34
31 95
33 95
33 98
34 98
34 4
35 4
35 74
36 74
36 84
37 84
37 17
48 17
48 76
49 76
49 71
50 71
50 27
54 27
54 99
60 99
60 23
62 23
62 78
63 78
63 44
66 44
66 73
67 73
67 33
72...

output:

189

result:

ok single line: '189'

Test #17:

score: 0
Accepted
time: 68ms
memory: 21072kb

input:

81 88 12 33
100
E 100
100 74
100 71
99 71
99 69
98 69
98 68
96 68
96 69
94 69
94 70
92 70
92 71
91 71
91 73
90 73
90 71
88 71
88 72
87 72
87 71
86 71
86 72
82 72
82 71
81 71
81 70
80 70
80 68
79 68
79 69
75 69
75 70
68 70
68 73
67 73
67 70
63 70
63 72
62 72
62 73
60 73
60 68
57 68
57 73
56 73
56 68
...

output:

212

result:

ok single line: '212'

Test #18:

score: 0
Accepted
time: 50ms
memory: 16920kb

input:

4 70 60 22
100
S 100
42 100
43 100
43 99
72 99
72 95
44 95
44 94
57 94
57 93
72 93
72 91
70 91
70 88
56 88
56 87
43 87
43 86
50 86
50 84
51 84
51 83
50 83
50 81
64 81
64 80
58 80
58 79
49 79
49 77
53 77
53 74
48 74
48 73
47 73
47 72
57 72
57 69
46 69
46 68
58 68
58 64
56 64
56 61
54 61
54 58
64 58
6...

output:

200

result:

ok single line: '200'

Test #19:

score: 0
Accepted
time: 67ms
memory: 24088kb

input:

19 81 54 90
95
N 100
1 38
1 81
2 81
2 69
4 69
4 78
5 78
5 50
9 50
9 73
11 73
11 99
14 99
14 84
16 84
16 40
18 40
18 49
20 49
20 85
21 85
21 99
27 99
27 49
29 49
29 74
31 74
31 94
33 94
33 65
34 65
34 55
35 55
35 86
38 86
38 79
39 79
39 51
44 51
44 75
46 75
46 48
49 48
49 81
53 81
53 87
56 87
56 70
5...

output:

125

result:

ok single line: '125'

Test #20:

score: 0
Accepted
time: 104ms
memory: 52088kb

input:

1 50 100 50
20
W 32
37 73
37 79
49 79
49 77
50 77
50 85
58 85
58 72
66 72
66 70
62 70
62 67
60 67
60 66
58 66
58 65
57 65
57 64
51 64
51 63
53 63
53 57
49 57
49 58
41 58
41 68
42 68
42 69
39 69
39 71
41 71
41 73
W 26
37 26
37 31
46 31
46 35
54 35
54 36
63 36
63 31
69 31
69 29
71 29
71 25
76 25
76 17...

output:

121

result:

ok single line: '121'

Test #21:

score: 0
Accepted
time: 9ms
memory: 20140kb

input:

1 50 100 50
20
W 32
16 55
16 61
19 61
19 67
20 67
20 70
22 70
22 73
32 73
32 59
30 59
30 53
41 53
41 52
42 52
42 53
44 53
44 52
53 52
53 36
40 36
40 51
39 51
39 47
36 47
36 43
24 43
24 50
22 50
22 53
19 53
19 55
W 24
4 30
4 47
14 47
14 57
12 57
12 67
24 67
24 63
31 63
31 58
35 58
35 56
25 56
25 57
2...

output:

178

result:

ok single line: '178'

Test #22:

score: 0
Accepted
time: 118ms
memory: 38188kb

input:

1 50 5 90
100
W 24
37 32
37 43
47 43
47 45
49 45
49 37
52 37
52 34
53 34
53 35
54 35
54 42
56 42
56 38
62 38
62 28
56 28
56 24
54 24
54 22
47 22
47 24
41 24
41 32
N 24
11 57
11 59
21 59
21 63
23 63
23 64
28 64
28 57
30 57
30 53
33 53
33 54
44 54
44 48
34 48
34 43
23 43
23 50
21 50
21 52
19 52
19 55
...

output:

106

result:

ok single line: '106'

Test #23:

score: 0
Accepted
time: 52ms
memory: 55600kb

input:

1 2 1 3
1
N 4
1 4
2 4
2 1
1 1

output:

1

result:

ok single line: '1'

Test #24:

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

input:

1 50 100 50
50
W 14
48 57
48 77
56 77
56 89
72 89
72 88
79 88
79 66
65 66
65 57
61 57
61 50
57 50
57 57
W 26
54 52
54 73
73 73
73 55
81 55
81 49
95 49
95 34
80 34
80 31
83 31
83 29
86 29
86 8
79 8
79 19
74 19
74 21
63 21
63 13
60 13
60 25
62 25
62 49
71 49
71 52
W 22
18 42
18 62
28 62
28 43
47 43
47...

output:

193

result:

ok single line: '193'

Test #25:

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

input:

1 50 100 50
20
W 32
68 67
68 69
75 69
75 71
73 71
73 75
68 75
68 77
73 77
73 78
68 78
68 84
69 84
69 90
70 90
70 96
73 96
73 95
74 95
74 90
77 90
77 92
87 92
87 89
95 89
95 77
85 77
85 76
90 76
90 73
85 73
85 67
W 34
36 9
36 18
40 18
40 24
43 24
43 26
40 26
40 33
52 33
52 38
48 38
48 46
54 46
54 42
...

output:

150

result:

ok single line: '150'

Test #26:

score: 0
Accepted
time: 12ms
memory: 18860kb

input:

1 50 100 50
20
W 22
34 59
34 71
41 71
41 79
50 79
50 69
46 69
46 61
53 61
53 57
58 57
58 55
59 55
59 48
57 48
57 44
49 44
49 48
38 48
38 57
41 57
41 59
W 22
76 42
76 58
79 58
79 62
80 62
80 65
81 65
81 71
88 71
88 72
92 72
92 68
98 68
98 61
92 61
92 60
98 60
98 54
87 54
87 52
86 52
86 42
W 28
31 55
...

output:

188

result:

ok single line: '188'

Test #27:

score: 0
Accepted
time: 8ms
memory: 25420kb

input:

1 50 100 50
20
W 26
46 31
46 44
51 44
51 33
60 33
60 21
71 21
71 14
68 14
68 13
71 13
71 9
68 9
68 3
66 3
66 2
56 2
56 12
54 12
54 15
56 15
56 16
48 16
48 23
47 23
47 31
W 32
59 56
59 63
70 63
70 60
71 60
71 65
77 65
77 73
79 73
79 65
82 65
82 63
85 63
85 58
91 58
91 60
95 60
95 58
98 58
98 50
90 50...

output:

176

result:

ok single line: '176'

Test #28:

score: 0
Accepted
time: 25ms
memory: 26240kb

input:

1 50 100 50
50
W 30
60 63
60 71
68 71
68 76
66 76
66 78
63 78
63 88
66 88
66 89
74 89
74 88
81 88
81 82
74 82
74 78
84 78
84 77
86 77
86 74
76 74
76 72
81 72
81 69
80 69
80 61
74 61
74 68
73 68
73 63
W 22
38 65
38 71
45 71
45 75
40 75
40 79
43 79
43 84
45 84
45 88
50 88
50 84
54 84
54 88
56 88
56 91...

output:

179

result:

ok single line: '179'

Test #29:

score: 0
Accepted
time: 49ms
memory: 23992kb

input:

1 50 100 50
100
E 28
59 44
59 56
66 56
66 60
80 60
80 58
82 58
82 51
86 51
86 49
96 49
96 46
98 46
98 36
91 36
91 43
90 43
90 42
84 42
84 35
92 35
92 32
82 32
82 34
74 34
74 39
65 39
65 44
S 26
33 49
33 53
39 53
39 54
48 54
48 55
46 55
46 58
48 58
48 62
60 62
60 60
63 60
63 66
70 66
70 53
72 53
72 3...

output:

191

result:

ok single line: '191'

Test #30:

score: 0
Accepted
time: 49ms
memory: 32116kb

input:

50 5 90 5
100
S 20
63 37
63 43
78 43
78 41
79 41
79 54
84 54
84 49
93 49
93 35
92 35
92 23
80 23
80 28
74 28
74 33
80 33
80 35
72 35
72 37
N 34
57 36
57 47
62 47
62 52
68 52
68 62
76 62
76 71
92 71
92 60
79 60
79 46
73 46
73 40
82 40
82 44
84 44
84 40
86 40
86 33
88 33
88 31
90 31
90 26
82 26
82 29
...

output:

117

result:

ok single line: '117'

Test #31:

score: 0
Accepted
time: 320ms
memory: 59004kb

input:

1 50 100 50
100
E 16
87 75
87 80
92 80
92 77
93 77
93 74
96 74
96 70
95 70
95 66
94 66
94 65
90 65
90 72
89 72
89 75
S 20
50 68
50 72
53 72
53 75
56 75
56 78
59 78
59 70
58 70
58 69
62 69
62 67
59 67
59 65
56 65
56 67
55 67
55 65
52 65
52 68
E 10
44 29
44 35
53 35
53 33
52 33
52 25
51 25
51 24
48 24...

output:

115

result:

ok single line: '115'

Test #32:

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

input:

0 0 0 1
1
W 4
1 1
1 0
0 0
0 1

output:

2

result:

ok single line: '2'

Test #33:

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

input:

20 1 1 10
2
E 4
1 30
15 30
15 0
1 0
S 4
0 29
100 29
100 22
0 22

output:

32

result:

ok single line: '32'

Test #34:

score: 0
Accepted
time: 127ms
memory: 69760kb

input:

42 42 42 42
0

output:

0

result:

ok single line: '0'

Test #35:

score: 0
Accepted
time: 6ms
memory: 16996kb

input:

0 0 100 100
4
N 4
0 0
0 100
100 100
100 0
E 4
0 0
0 100
100 100
100 0
W 4
0 0
0 100
100 100
100 0
S 4
0 0
0 100
100 100
100 0

output:

300

result:

ok single line: '300'

Test #36:

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

input:

50 0 50 100
1
S 4
0 20
60 20
60 100
0 100

output:

120

result:

ok single line: '120'

Test #37:

score: 0
Accepted
time: 82ms
memory: 67756kb

input:

50 0 50 100
1
S 4
0 20
100 20
100 21
0 21

output:

101

result:

ok single line: '101'