题目
https://codeforces.com/contest/1428/problem/D
思路
构造，对于每一个$a_i$，考虑$a_j(1 \leq j <i)$与$a_i$配对，2与1配成一对，3与3、2和1配成一对。如果存在2或者3没有相应的$a_i$与之配对，则输出-1。否则输出每一对的坐标。
AC代码
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } }_io;
typedef long long ll; typedef long double db;
const ll maxn = 1e5 + 5;
array<ll, maxn> tar;
int main()
{
ll n;
cin >> n;
deque<ll> p2, p3;
vector<pair<ll, ll>> comb;
for (ll i = 1; i <= n; ++i)
{
cin >> tar[i];
if (tar[i] == 2) p2.push_back(i);
else if (tar[i] == 3) p3.push_back(i);
if (tar[i] == 1)
{
if (!p2.empty())
{
comb.push_back({ *p2.begin(),i });
p2.pop_front();
}
else if (!p3.empty())
{
comb.push_back({ *p3.begin(),i });
p3.pop_front();
}
else
{
comb.push_back({ i,i });
}
}
if (tar[i] == 2 && !p3.empty())
{
comb.push_back({ *p3.begin(),i });
p3.pop_front();
}
if (tar[i] == 3 && !p3.empty() && *p3.begin() != i)
{
comb.push_back({ *p3.begin(),i });
p3.pop_front();
}
}
if (!p2.empty() || !p3.empty())
{
cout << -1 << endl;
return 0;
}
if (comb.empty())
{
cout << 0 << endl;
return 0;
}
ll level = 1, ans = 0;
for (auto &i : comb)
{
if (tar[i.first] == 1) ++ans;
else if (tar[i.first] == 2)
{
ans += 2;
}
else if (tar[i.first] == 3)
{
if (tar[i.second] == 1) ans += 3;
else if (tar[i.second] == 2 || tar[i.second] == 3) ans += 2;
}
}
cout << ans << endl;
for (auto &i : comb)
{
if (tar[i.first] == 1)
{
cout << level << " " << i.first << endl;
++level;
}
else if (tar[i.first] == 2)
{
cout << level << " " << i.first << endl;
cout << level << " " << i.second << endl;
++level;
}
else if (tar[i.first] == 3)
{
if (tar[i.second] == 1)
{
cout << level << " " << i.first << endl;
cout << level << " " << i.second << endl;
cout << level + 1 << " " << i.second << endl;
level += 2;
}
else if (tar[i.second] == 2 || tar[i.second] == 3)
{
cout << level << " " << i.first << endl;
cout << level << " " << i.second << endl;
++level;
}
}
}
return 0;
}
|