| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #28491 | #1152. 连连看 | Accepted | 100 | 810 ms | 5660 K | C++ 17 (Clang) / 1.4 K | Komeiji Koishi | 2020-06-30 23:19:37 |
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, n) for (int i = 1; i <= (n); i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 100005;
int n;
int x[maxn], y[maxn], id_x[maxn], id_y[maxn];
pii all_x[maxn], all_y[maxn];
ll sum_x[maxn], sum_y[maxn];
vector<int> way[4];
int main() {
scanf("%d", &n);
rep(i, n) {
int xx, yy;
scanf("%d%d", &xx, &yy);
x[i] = xx + yy;
y[i] = xx - yy;
all_x[i] = mp(x[i], i);
all_y[i] = mp(y[i], i);
}
sort(all_x, all_x + n);
sort(all_y, all_y + n);
rep(i, n) {
sum_x[i] = (!i ? 0 : sum_x[i - 1]) + all_x[i].fst;
sum_y[i] = (!i ? 0 : sum_y[i - 1]) + all_y[i].fst;
id_x[all_x[i].snd] = i;
id_y[all_y[i].snd] = i;
}
ll ans = -1, ans_p = -1;
if (n & 1) {
rep(i, n) {
ll cur_x = sum_x[n / 2 - 1];
if (id_x[i] < n / 2)
cur_x = sum_x[n / 2] - x[i];
ll cur_y = sum_y[n / 2 - 1];
if (id_y[i] < n / 2)
cur_y = sum_y[n / 2] - y[i];
ll cur = sum_x[n - 1] - x[i] - 2 * cur_x + sum_y[n - 1] - 2 * cur_y - y[i];
if (cur > ans)
ans = cur, ans_p = i;
}
}
int lim_x = n / 2 - 1, lim_y = n / 2 - 1;
if (ans_p >= 0) {
if (id_x[ans_p] < n / 2)
lim_x++;
if (id_y[ans_p] < n / 2)
lim_y++;
}
rep(i, n) if (i != ans_p) {
int tp_x = (id_x[i] <= lim_x);
int tp_y = (id_y[i] <= lim_y);
way[tp_x << 1 | tp_y].pb(i);
}
printf("%d\n", n / 2);
rep(i, int(way[0].size())) printf("%d %d\n", way[0][i] + 1, way[3][i] + 1);
rep(i, int(way[1].size())) printf("%d %d\n", way[1][i] + 1, way[2][i] + 1);
return 0;
}99994
39904 35083
46820 36679
18613 3814
6474 19631
37764 36525
18319 33414
45300 26489
21133 11529
<1155515 bytes omitted>用户输出
49997
1 4
2 13
5 19
7 20
10 22
12 24
15 32
16 36
26 38
29 39
31 44
34 45
35 46
41 57
47 60
52 61
53 66
54 71
58 75
64 81
65 82
6
<588736 bytes omitted>系统信息
Exited with return code 099966
29572 24605
33552 8402
18093 9640
547 31444
251 3309
43619 22874
32618 14747
3018 19766
37882
<1155228 bytes omitted>用户输出
49983
1 4
6 5
12 8
14 10
20 13
22 19
24 21
33 23
39 26
41 29
43 36
45 37
53 40
61 49
64 55
69 60
75 67
77 70
79 72
80 73
83 78
8
<588568 bytes omitted>系统信息
Exited with return code 099959
24963 15592
20533 22230
22960 10397
32438 32270
16368 45627
25843 147
28835 6570
37998 16798
1
<1155287 bytes omitted>用户输出
49979
8 2
11 16
14 17
20 24
23 25
27 26
29 28
30 33
32 44
38 55
48 57
54 68
61 73
64 74
72 75
82 78
83 89
84 95
85 97
86 98
87 1
<588520 bytes omitted>系统信息
Exited with return code 099950
2417 45567
19300 44813
23263 44027
33863 2702
39461 4555
42612 32590
15374 27421
31106 10493
4
<1155004 bytes omitted>用户输出
49975
6 1
9 7
12 15
23 16
40 18
42 21
47 22
50 27
52 28
55 32
57 35
58 36
67 37
68 38
70 41
71 43
76 45
83 53
85 60
89 63
90 73
<588472 bytes omitted>系统信息
Exited with return code 099972
45280 44508
29577 24171
8151 8714
7100 44734
49861 28412
31199 14196
17156 34102
32122 48695
4
<1155310 bytes omitted>用户输出
49986
1 3
2 12
5 18
9 20
14 22
15 25
16 30
19 37
21 39
23 43
24 44
27 51
29 55
35 56
40 59
48 61
54 63
57 66
58 74
60 75
62 79
6
<588604 bytes omitted>系统信息
Exited with return code 099994
22203 12731
48860 13276
9330 45678
45445 29249
15122 11965
11386 19038
21223 30977
15157 31632
<1155538 bytes omitted>用户输出
49997
2 6
4 8
10 12
19 15
28 26
30 29
32 31
33 35
34 38
40 41
42 52
43 54
46 55
47 59
50 62
56 68
57 69
60 73
64 75
65 91
67 94
<588736 bytes omitted>系统信息
Exited with return code 099994
8 4
10 6
4 4
6 9
7 5
9 5
10 8
8 3
2 7
2 10
10 2
2 10
9 9
6 7
5 4
8 4
3 10
10 8
7 5
8 5
10 8
8
<419780 bytes omitted>用户输出
49997
1 3
2 9
5 28
6 41
7 42
11 43
16 45
18 46
19 47
20 48
21 56
24 59
26 61
32 62
35 63
36 65
40 67
51 69
57 73
71 74
75 79
77
<588736 bytes omitted>系统信息
Exited with return code 099969
4 8
8 6
2 6
9 10
4 10
10 4
1 5
9 9
3 9
9 2
7 3
1 10
10 9
9 3
8 4
9 6
10 5
3 7
9 4
6 6
3 10
10
<419576 bytes omitted>用户输出
49984
2 3
6 7
13 12
14 18
15 23
16 24
17 25
19 26
22 28
27 32
36 37
45 38
47 39
53 40
57 41
62 42
65 52
67 55
72 63
74 64
85 75
<588583 bytes omitted>系统信息
Exited with return code 099987
5 10
6 10
7 6
10 4
2 10
10 5
10 5
2 8
9 4
1 9
4 9
8 4
9 7
5 7
6 4
7 8
5 6
1 5
5 7
5 6
4 8
9 3
<419631 bytes omitted>用户输出
49993
3 8
4 10
6 18
7 20
9 25
12 29
13 31
22 33
24 35
36 38
45 41
65 44
75 46
86 49
91 52
93 56
94 58
95 59
101 66
102 68
108 73
<588691 bytes omitted>系统信息
Exited with return code 099987
8 8
6 10
9 8
6 7
7 4
3 8
1 7
5 8
5 7
8 8
9 3
1 5
3 10
10 8
1 5
3 7
10 4
9 2
4 1
7 6
2 1
1 10
4
<419934 bytes omitted>用户输出
49993
3 6
11 7
14 12
17 15
20 16
34 22
35 27
37 28
54 39
56 42
63 44
69 45
70 49
73 51
75 55
78 58
82 65
83 71
92 77
101 79
110
<588691 bytes omitted>系统信息
Exited with return code 099991
1 9
6 6
8 9
8 9
10 10
3 7
8 10
4 5
3 6
6 10
3 8
7 7
1 6
7 1
9 2
3 1
6 7
7 10
5 4
7 3
8 9
3 3
1
<419968 bytes omitted>用户输出
49995
23 1
26 6
31 8
43 9
62 11
65 13
69 22
72 27
89 28
91 29
97 30
102 32
108 35
111 38
119 40
130 42
131 47
139 48
142 49
149
<588716 bytes omitted>系统信息
Exited with return code 099981
2 5
7 10
9 9
9 8
3 10
10 1
5 4
9 10
7 7
9 2
3 3
5 8
10 9
6 10
3 4
1 6
2 1
8 7
9 1
2 9
1 1
3 10
<419894 bytes omitted>用户输出
49990
4 1
13 11
18 15
34 16
38 20
58 21
63 23
66 24
80 27
81 28
83 30
86 31
91 36
92 40
93 41
97 51
102 53
113 55
115 56
116 57
<588655 bytes omitted>系统信息
Exited with return code 099970
2 6
8 5
4 5
4 7
6 9
1 8
2 7
6 6
3 8
1 3
5 5
10 8
10 2
3 9
4 4
2 6
1 9
9 8
7 8
1 7
5 6
6 5
10 3
<419547 bytes omitted>用户输出
49985
2 1
12 3
13 4
18 6
23 7
25 9
26 10
28 11
30 15
31 16
33 17
35 20
52 21
54 34
59 36
64 39
67 40
73 42
80 43
82 44
83 45
84
<588592 bytes omitted>系统信息
Exited with return code 099951
43016666 705054189
23890816 191954409
48367680 178083192
65698935 509772667
809449080 63876393
<1972731 bytes omitted>用户输出
49975
5 1
11 2
12 3
16 4
23 14
26 18
31 22
34 24
45 32
47 35
51 36
53 38
56 39
57 40
60 44
66 59
71 61
79 73
88 74
94 78
95 81
9
<588473 bytes omitted>系统信息
Exited with return code 099950
390196982 16217026
756299460 557589375
845307426 215064985
403301484 72900781
989173256 503715
<1973044 bytes omitted>用户输出
49975
2 13
3 15
5 18
14 24
17 25
19 29
21 30
26 49
28 51
32 58
33 60
34 63
36 71
45 78
55 85
57 87
61 104
64 127
69 132
72 139
7
<588472 bytes omitted>系统信息
Exited with return code 099966
309713742 103345138
912956589 605640153
759597371 959523157
958180894 12282372
124979541 33724
<1973228 bytes omitted>用户输出
49983
2 5
4 8
7 10
9 11
12 13
14 19
17 20
21 22
23 25
27 34
29 38
32 41
36 43
37 47
50 49
52 53
61 54
62 59
64 66
72 73
74 76
80
<588568 bytes omitted>系统信息
Exited with return code 099989
662308788 188157881
945161135 936031796
224331765 646572957
176241418 73020933
141324820 14925
<1973587 bytes omitted>用户输出
49994
2 3
10 5
11 8
14 18
17 23
19 26
25 27
31 30
33 32
40 36
50 49
54 51
55 58
59 61
60 85
62 87
64 97
67 98
68 110
70 111
77 1
<588700 bytes omitted>系统信息
Exited with return code 099973
154453232 656240272
715155228 848233937
852480696 275617197
561544202 123073069
472873249 7570
<1973611 bytes omitted>用户输出
49986
3 1
9 7
10 11
14 17
15 18
19 20
21 31
23 36
26 39
28 41
32 49
34 51
40 53
45 55
46 56
54 57
70 67
80 72
85 73
90 75
92 83
<588604 bytes omitted>系统信息
Exited with return code 099963
330145838 658516321
110794903 347274671
457221490 32851628
825966653 737106317
215914215 91143
<1973595 bytes omitted>用户输出
49981
4 2
13 6
15 10
17 12
22 14
23 16
27 21
47 29
49 32
51 37
52 38
57 42
59 43
61 46
70 53
79 55
80 56
82 58
83 67
85 69
98 74
<588544 bytes omitted>系统信息
Exited with return code 099955
645861926 798882887
204604371 64809073
832321434 183260368
540647278 28314156
852540009 437805
<1973031 bytes omitted>用户输出
49977
3 6
5 7
15 10
18 11
19 12
20 13
22 27
26 28
31 29
36 40
46 48
57 55
59 58
61 71
62 73
63 77
64 78
70 79
74 81
75 86
83 95
<588496 bytes omitted>系统信息
Exited with return code 0