1407.md (6044B)
1 Source: https://codeforces.com/blog/entry/82417 2 3 [1407A — Ahahahahahahahaha](https://codeforces.com/contest/1407/problem/A) 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int main() { 16 int t; 17 cin >> t; 18 while (t--) { 19 int n; 20 cin >> n; 21 vector<int>a(n), ans; 22 int cnt0 = 0; 23 for (int i = 0; i < n; i++) { 24 cin >> a[i]; 25 if (!a[i]) cnt0++; 26 } 27 int cnt1 = n - cnt0; 28 if (cnt0 >= n / 2) { 29 cout << cnt0 << '\n'; 30 for (int i = 0; i < cnt0; i++) cout << 0 << ' '; 31 } else { 32 cout << cnt1 - cnt1 % 2 << '\n'; 33 for (int i = 0; i < cnt1 - cnt1 % 2; i++) { 34 cout << 1 << ' '; 35 } 36 } 37 cout << '\n'; 38 } 39 return 0; 40 } 41 ``` 42 43 [1407B — Big Vova](https://codeforces.com/contest/1407/problem/B) 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 56 void solve() { 57 int n; 58 cin >> n; 59 int a[n]; 60 int mi = 0; 61 for (int i = 0; i < n; i++) { 62 cin >> a[i]; 63 mi = (a[i] > a[mi] ? i : mi); 64 } 65 vector<int> b(n); 66 b[0] = a[mi]; a[mi] = 0; 67 int cg = b[0]; 68 for (int i = 1; i < n; i++) { 69 int ci = 0, cans = 0; 70 for (int j = 0; j < n; j++) 71 if (a[j] && __gcd(a[j], cg) > cans) { 72 cans = __gcd(a[j], cg); 73 ci = j; 74 } 75 b[i] = a[ci]; 76 cg = cans; 77 a[ci] = 0; 78 } 79 for (int i = 0; i < n; i++) 80 cout << b[i] << ' '; 81 cout << '\n'; 82 } 83 84 int main() { 85 int t; 86 cin >> t; 87 while (t--) 88 solve(); 89 return 0; 90 } 91 ``` 92 93 [1407C — Chocolate Bunny](https://codeforces.com/contest/1407/problem/C) 94 95 **Tutorial** 96 97 Tutorial is loading... 98 99 **Solution** 100 101 ``` 102 #include <bits/stdc++.h> 103 using namespace std; 104 int ask(int x, int y) { 105 cout << "? " << x + 1 << ' ' << y + 1 << endl; 106 int z; 107 cin >> z; 108 return z; 109 } 110 int main() { 111 int n; 112 cin >> n; 113 vector<int>ans(n, -1); 114 int mx = 0; 115 for (int i = 1; i < n; i++) { 116 int a = ask(mx, i); 117 int b = ask(i, mx); 118 if (a > b) { 119 ans[mx] = a; 120 mx = i; 121 } else { 122 ans[i] = b; 123 } 124 } 125 ans[mx] = n; 126 cout << "! "; 127 for (int i = 0; i < n; i++) cout << ans[i] << ' '; 128 cout << endl; 129 return 0; 130 } 131 ``` 132 133 [1407D — Discrete Centrifugal Jumps](https://codeforces.com/contest/1407/problem/D) 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution** 140 141 ``` 142 #include <bits/stdc++.h> 143 using namespace std; 144 const int INF = 1e9 + 1; 145 const int maxn = 3e5 + 1; 146 int h[maxn], dp[maxn], lge[maxn], lle[maxn], rge[maxn], rle[maxn]; 147 vector<int>jumps[maxn]; 148 int main() { 149 int n; 150 cin >> n; 151 for (int i = 0; i < n; i++) { 152 cin >> h[i]; 153 dp[i] = INF; 154 } 155 dp[0] = 0; 156 vector<pair<int, int> >st; 157 for (int i = 0; i < n; i++) { // the nearest greater from the left 158 while (!st.empty() && st.back().first < h[i]) { 159 st.pop_back(); 160 } 161 if (st.empty()) lge[i] = -1; 162 else lge[i] = st.back().second; 163 st.push_back({h[i], i}); 164 } 165 st.clear(); 166 for (int i = 0; i < n; i++) { // the nearest less from the left 167 while (!st.empty() && st.back().first > h[i]) { 168 st.pop_back(); 169 } 170 if (st.empty()) lle[i] = -1; 171 else lle[i] = st.back().second; 172 st.push_back({h[i], i}); 173 } 174 st.clear(); 175 for (int i = n - 1; i >= 0; i--) { // the nearest greater from the right 176 while (!st.empty() && st.back().first < h[i]) { 177 st.pop_back(); 178 } 179 if (st.empty()) rge[i] = -1; 180 else rge[i] = st.back().second; 181 st.push_back({h[i], i}); 182 } 183 st.clear(); 184 for (int i = n - 1; i >= 0; i--) { // the nearest less from the right 185 while (!st.empty() && st.back().first > h[i]) { 186 st.pop_back(); 187 } 188 if (st.empty()) rle[i] = -1; 189 else rle[i] = st.back().second; 190 st.push_back({h[i], i}); 191 } 192 st.clear(); 193 for (int i = 0; i < n; i++) { 194 if (rle[i] != -1) jumps[i].push_back(rle[i]); 195 if (rge[i] != -1) jumps[i].push_back(rge[i]); 196 if (lle[i] != -1) jumps[lle[i]].push_back(i); 197 if (lge[i] != -1) jumps[lge[i]].push_back(i); 198 } 199 for (int i = 0; i < n; i++) { 200 for (int to : jumps[i]) { 201 dp[to] = min(dp[to], dp[i] + 1); 202 } 203 } 204 cout << dp[n - 1]; 205 return 0; 206 } 207 ``` 208 209 [1407E — Egor in the Republic of Dagestan](https://codeforces.com/contest/1407/problem/E) 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 const int maxn = 1e6 + 1; 223 224 vector<int> bg[maxn], rg[maxn]; 225 int b[maxn], r[maxn], d[maxn], col[maxn]; 226 int n, m; 227 228 int main() { 229 ios_base::sync_with_stdio(0); 230 cin.tie(0); cout.tie(0); 231 cin >> n >> m; 232 for (int i = 0; i < m; i++) { 233 int u, v, t; 234 cin >> u >> v >> t; 235 --u; --v; 236 if (!t) bg[v].push_back(u); 237 else rg[v].push_back(u); 238 } 239 for (int i = 0; i < n; i++) 240 d[i] = b[i] = r[i] = n; 241 queue<int> q; 242 q.push(n - 1); 243 d[n - 1] = r[n - 1] = b[n - 1] = 0; 244 while (!q.empty()) { 245 int x = q.front(); 246 q.pop(); 247 for (auto to : bg[x]) { 248 if (b[to] < n) continue; 249 b[to] = d[x] + 1; 250 if (max(b[to], r[to]) < n) { 251 q.push(to); 252 d[to] = max(b[to], r[to]); 253 } 254 } 255 for (auto to : rg[x]) { 256 if (r[to] < n) continue; 257 r[to] = d[x] + 1; 258 if (max(b[to], r[to]) < n) { 259 q.push(to); 260 d[to] = max(b[to], r[to]); 261 } 262 } 263 } 264 if (d[0] == n) cout << "-1\n"; 265 else cout << d[0] << '\n'; 266 for (int i = 0; i < n; i++) { 267 if (b[i] > r[i]) col[i] = 0; 268 else col[i] = 1; 269 cout << col[i]; 270 } 271 return 0; 272 } 273 ```