# # Codeforces Round 669 (CF1407) 题解

## # Problem A - Ahahahahahahahaha (opens new window)

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
int z = 0;
for (int i = 0; i < n; ++i)
read(a[i]), z += (a[i] == 0);
int k = z, d = 0;
if (z < n - z) {
d = 1;
k = n - z;
if (k % 2 == 1)
k--;
}
printf("%d\n", k);
vector<int> ans(k, d);
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem B - Big Vova (opens new window)

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
vector<bool> vis(n);
vector<int> ans(n);
int g = 0;
for (int i = 0; i < n; ++i) {
int hi = -1, hidx = -1;
for (int j = 0; j < n; ++j) {
if (vis[j])
continue;
int gj = gcd(g, a[j]);
if (gj > hi) {
hi = gj;
hidx = j;
}
}
ans[i] = a[hidx];
vis[hidx] = true;
g = hi;
}
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem C - Chocolate Bunny (opens new window)

### # 题解

#include <iostream>
#include <vector>

using namespace std;

class Solution {
vector<int> ans;

int query(int i, int j) {
int k;
cout << "? " << i << " " << j << endl;
cin >> k;
return k;
}

public:
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "! 1" << endl;
return;
}
ans = vector<int>(n + 1);
int a = query(1, 2), b = query(2, 1);
int m;
if (a > b) {
m = 2;
ans[1] = a;
} else {
m = 1;
ans[2] = b;
}
for (int i = 3; i <= n; ++i) {
int a = query(m, i), b = query(i, m);
if (a > b) {
ans[m] = a;
m = i;
} else {
ans[i] = b;
}
}
ans[m] = n;
cout << "! ";
for (int i = 1; i <= n; ++i)
cout << ans[i] << " ";
cout << endl;
}
};

int main() {
Solution solution = Solution();
solution.solve();
}
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

## # Problem D - Discrete Centrifugal Jumps (opens new window)

### # 题目描述

• $i+1=j$
• $\min(h_i,h_j)>\max_{k=i+1}^{j-1} h_k$
• $\max(h_i,h_j)<\min_{k=i+1}^{j-1} h_k$

### # 题解

• $h_j$$h_i$右边第一个不小于$h_i$
• $h_j$$h_i$右边第一个不大于$h_i$
• $h_i$$h_j$左边第一个不小于$h_j$
• $h_i$$h_j$左边第一个不大于$h_j$

#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {

public:
void solve() {
int n;
vector<int> h(n);
for (int i = 0; i < n; ++i)
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] <= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] >= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] <= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] >= h[st.top()]) {
st.pop();
}
st.push(i);
}
queue<int> q;
q.push(0);
vector<int> dist(n, -1);
dist[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == n - 1) {
printf("%d", dist[u]);
return;
}
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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

## # Problem E - Egor in the Republic of Dagestan (opens new window)

### # 题解

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {

public:
void solve() {
int n, m;
vector<vector<pair<int, int>>> in(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, t;
if (u == v)
continue;
t++;
in[v].emplace_back(u, t);
}

queue<pair<int, int>> q;
q.emplace(n, 0);
vector<int> close(n + 1);
vector<int> dist(n + 1);
vector<bool> vis(n + 1);
vis[n] = true;
while (!q.empty()) {
auto [v, d] = q.front();
dist[v] = d;
q.pop();
for (auto [u, t] : in[v]) {
if (vis[u])
continue;
if ((t == 1 && close[u] == 2) || (t == 2 && close[u] == 1)) {
vis[u] = true;
q.emplace(u, d + 1);
} else
close[u] = t;
}
}
if (!vis[1])
printf("-1\n");
else
printf("%d\n", dist[1]);
for (int i = 1; i <= n; ++i)
printf("%d", min(1, 2 - close[i]));
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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