Submission #60694

ソースコード

?
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
81
#include <iostream>
#include <limits>
#include <cassert>
#include <map>
using namespace std;
signed main()
{
int N, Q;
cin >> N >> Q;
assert(2 <= N && N <= 1e3);
assert(1 <= Q && Q <= 1e3);
map<pair<int, int>, bool> used;
used[{1,1}] = true;
// x, y の入力
int x[N], y[N];
for(int i = 0; i < N; ++i){
cin >> x[i] >> y[i];
assert(1 <= x[i] && x[i] <= 1e9 && 1 <= y[i] && y[i] <= 1e9);
if(used[{x[i], y[i]}]){
cout << x[i] << ' ' << y[i] << '\n';
assert(false);
}else{
used[{x[i], y[i]}] = true;
}
}
// (now_,now_y)：現在いる交差点
// sum：通った道路の本数
int now_x = 1, now_y = 1;
int64_t sum = 0;
for(int i = 0; i < Q; ++i){
// count：距離がkに最も近い観光スポットの個数
// (min_x,min_y)：距離が最もkに近い観光スポットのある交差点
// min_dist：(min_x,min_y)への距離とkとの差の絶対値(この値が小さいほどkに近い),初期値はとても大きい値にしておく
int64_t k, min_dist = 20000000000;
int count = 0, min_x, min_y;
cin >> k;
assert(1 <= k && k <= 1e10);
// 全ての観光スポットを見て、最も距離がkに近い観光スポットを探す
for(int j = 0; j < N; ++j){
// 今いる観光スポットは見ない(距離が1以上を満たさないため)
if(!(x[j] == now_x && y[j] == now_y)){
// j番目の観光スポット方への距離が、現在最小としているmin_distの値よりも小さい場合
// abs(k - abs(now_x - x[j]) + abs(now_y - y[j]))：(x[j],y[j])への距離とkとの差の絶対値
if(min_dist > abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])))){
count = 1;
min_dist = abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])));
min_x = x[j];
min_y = y[j];
// j番目観光スポットへの距離が、min_distと等しい場合(距離が最小の観光スポットが複数ある場合)
}else if(min_dist == abs(k - (abs(now_x - x[j]) + abs(now_y - y[j])))){
++count;
}
}
}
// 距離がkに近い観光スポットが一つの場合
if(count == 1){
sum += abs(now_x - min_x) + abs(now_y - min_y);
now_x = min_x;
now_y = min_y;
// 距離がkに近い観光スポットが複数ある場合
}else{
sum += abs(now_x - 1) + abs(now_y - 1);
now_x = 1;
now_y = 1;
}
}
cout << sum << '\n';
return (0);
}

ステータス

項目 データ
問題 1354 - 山田之国
ユーザー名 ei1903
投稿日時 2020-07-12 22:38:53
言語 C++17
状態 Accepted
得点 50
ソースコード長 2883 Byte
最大実行時間 30 ms
最大メモリ使用量 732 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 24 ms 604 KB
1
in02.txt AC 22 ms 660 KB
1
in03.txt AC 30 ms 456 KB
1
in04.txt AC 27 ms 488 KB
1
in05.txt AC 23 ms 512 KB
1
in06.txt AC 27 ms 544 KB
1
in07.txt AC 27 ms 580 KB
1
in08.txt AC 25 ms 620 KB
1
in09.txt AC 24 ms 528 KB
1
in10.txt AC 24 ms 428 KB
1
in11.txt AC 25 ms 464 KB
1
in12.txt AC 24 ms 692 KB
1
in13.txt AC 18 ms 604 KB
1
in14.txt AC 22 ms 636 KB
1
in15.txt AC 19 ms 676 KB
1
in16.txt AC 23 ms 584 KB
1
in17.txt AC 21 ms 688 KB
1
in18.txt AC 22 ms 660 KB
1
in19.txt AC 22 ms 632 KB
1
in20.txt AC 28 ms 732 KB
1
in21.txt AC 21 ms 508 KB
1
sample01.txt AC 17 ms 612 KB
1
sample02.txt AC 24 ms 588 KB
1