Submission #00134

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
int main() {
#define int long long
while (true) {
int n;
cin >> n;
if (n == 0) return 0;
int a, b, c = 0, d;
// cは向き。c=0:x+, c=1:y+, c=2:x-, c=3:y-
cin >> a >> b >> d;
unordered_map<int, set<int>> x;
unordered_map<int, set<int>> y;
// 障害物の位置及びあった多方向 -> 訪れた時の残り歩数
map<pair<pair<int, int>, int>, int> z;
for (int i = 0; i < n; i++) {
int f, g;
cin >> f >> g;
x[f].insert(g);
y[g].insert(f);
}
while (true) {
// 向いている方向にぶつかるまで進む
int h = 0;
if (c == 0) {
auto itr = y[b].upper_bound(a);
h = itr != y[b].end() ? *itr - a - 1 : -1;
}
if (c == 1) {
auto itr = x[a].upper_bound(b);
h = itr != x[a].end() ? *itr - b - 1 : -1;
}
if (c == 2) {
auto itr = (y[b].lower_bound(a));
if (itr != y[b].begin()) {
itr--;
h = a - *itr - 1;
} else
h = -1;
}
if (c == 3) {
auto itr = (x[a].upper_bound(b));
if (itr != x[a].begin()) {
itr--;
h = b - *itr - 1;
} else
h = -1;
}
if (h == -1 || h > d) h = d;
if (c == 0) {
a += h;
}
if (c == 1) {
b += h;
}
if (c == 2) {
a -= h;
}
if (c == 3) {
b -= h;
}
d -= h;
// ぶつからない or ぶつかるまでの移動量が足りない -> 解として出力
if (d == 0) {
cout << a << " " << b << "\n";
break;
}
// 同じようにぶつかったことがあるのなら記録と現在を比較し周期を割り出す
if (z.find({{a, b}, c}) != z.end()) {
int k = z[{{a, b}, c}] - d;
// 残りの移動量を周期でMODする
d %= k;
}
// ぶつかったことがないのなら記録する
z[{{a, b}, c}] = d;
// 向きを回転させる
c = (c + 1) % 4;
}
}
}

ステータス

項目 データ
問題 0009 - だんごむしではないむし
ユーザー名 ei2332
投稿日時 2025-03-28 13:32:57
言語 C++17
状態 Accepted
得点 40
ソースコード長 2646 Byte
最大実行時間 62 ms
最大メモリ使用量 732 KB

セット

セット 得点 Cases
1 ALL 40 / 40 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
D1 AC 62 ms 732 KB
1
D2 AC 56 ms 696 KB
1
D3 AC 55 ms 664 KB
1
D4 AC 49 ms 632 KB
1