1579.md (8810B)
1 Source: https://codeforces.com/blog/entry/95447 2 3 [1579A - Casimir's String Solitaire](/contest/1579/problem/A "Codeforces Round 744 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 string s; 23 cin >> s; 24 cout << (count(s.begin(), s.end(), 'B') * 2 == s.size() ? 25 "YES\n" : "NO\n"); 26 } 27 } 28 ``` 29 30 [1579B - Shifting Sort](/contest/1579/problem/B "Codeforces Round 744 (Div. 3)") 31 32 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution** 39 40 ``` 41 #include <bits/stdc++.h> 42 43 using namespace std; 44 45 typedef pair<int, int> pii; 46 47 int main() { 48 int t; 49 cin >> t; 50 while (t--) { 51 int n; 52 cin >> n; 53 vector<int> a(n); 54 vector<pii> actions; 55 for (int i = 0; i < n; i++) 56 cin >> a[i]; 57 58 for (int i = 0; i < n - 1; i++) { 59 int min_pos = i; 60 for (int j = i + 1; j < n; j++) 61 if (a[j] < a[min_pos]) 62 min_pos = j; 63 64 if (min_pos > i) { 65 actions.push_back({i, min_pos}); 66 int opt = a[min_pos]; 67 for (int j = min_pos; j > i; j--) 68 a[j] = a[j - 1]; 69 a[i] = opt; 70 } 71 } 72 73 cout << actions.size() << '\n'; 74 for (auto &lr: actions) { 75 cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n'; 76 } 77 } 78 79 } 80 ``` 81 82 [1579C - Ticks](/contest/1579/problem/C "Codeforces Round 744 (Div. 3)") 83 84 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <bits/stdc++.h> 94 95 using namespace std; 96 97 int main() { 98 int t; 99 cin >> t; 100 while (t--) { 101 int n, m, k; 102 cin >> n >> m >> k; 103 vector<vector<int>> status(n, vector<int>(m, 0)); 104 for (int i = 0; i < n; i++) { 105 string s; 106 cin >> s; 107 for (int j = 0; j < m; j++) 108 if (s[j] == '*') 109 status[i][j] = 1; 110 } 111 for (int i = n - 1; i > -1; i--) { 112 for (int j = 0; j < m; j++) { 113 if (status[i][j] == 0) 114 continue; 115 int len = 0; 116 while (j > len && j + len + 1 < m && i > len) { 117 if (status[i - len - 1][j - len - 1] == 0 || status[i - len - 1][j + len + 1] == 0) 118 break; 119 len++; 120 } 121 if (len >= k) { 122 for (int d = 0; d <= len; d++) { 123 status[i - d][j - d] = 2; 124 status[i - d][j + d] = 2; 125 } 126 } 127 } 128 } 129 bool ok = true; 130 for (int i = 0; i < n; i++) 131 for (int j = 0; j < m; j++) 132 if (status[i][j] == 1) 133 ok = false; 134 135 cout << (ok ? "YES" : "NO") << '\n'; 136 } 137 } 138 ``` 139 140 [1579D - Productive Meeting](/contest/1579/problem/D "Codeforces Round 744 (Div. 3)") 141 142 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 143 144 **Tutorial** 145 146 Tutorial is loading... 147 148 **Solution** 149 150 ``` 151 #include <bits/stdc++.h> 152 153 using namespace std; 154 155 typedef pair<int, int> pii; 156 157 int main() { 158 int t; 159 cin >> t; 160 while (t--) { 161 int n; 162 cin >> n; 163 auto cmp = [](pii const &x, pii const &y) { 164 return x > y; 165 }; 166 set<pii, decltype(cmp)> a(cmp); 167 vector<pii> answer; 168 for (int i = 0; i < n; i++) { 169 int ai; 170 cin >> ai; 171 if (ai > 0) 172 a.emplace(ai, i + 1); 173 } 174 while (a.size() > 1) { 175 auto p1 = *a.begin(); 176 a.erase(a.begin()); 177 auto p2 = *a.begin(); 178 a.erase(a.begin()); 179 answer.emplace_back(p1.second, p2.second); 180 if (p1.first > 1) a.emplace(p1.first - 1, p1.second); 181 if (p2.first > 1) a.emplace(p2.first - 1, p2.second); 182 } 183 cout << answer.size() << '\n'; 184 for (auto &p : answer) { 185 cout << p.first << ' ' << p.second << '\n'; 186 } 187 } 188 } 189 ``` 190 191 [1579E1 - Permutation Minimization by Deque](/contest/1579/problem/E1 "Codeforces Round 744 (Div. 3)") 192 193 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 194 195 **Tutorial** 196 197 Tutorial is loading... 198 199 **Solution** 200 201 ``` 202 #include <bits/stdc++.h> 203 204 using namespace std; 205 206 int main() { 207 int t; 208 cin >> t; 209 while (t--) { 210 int n, a; 211 cin >> n; 212 deque<int> d; 213 for (int i = 0; i < n; i++) { 214 cin >> a; 215 if (d.empty() || a < d[0]) 216 d.push_front(a); 217 else 218 d.push_back(a); 219 } 220 for (int x : d) 221 cout << x << ' '; 222 cout << '\n'; 223 } 224 } 225 ``` 226 227 [1579E2 - Array Optimization by Deque](/contest/1579/problem/E2 "Codeforces Round 744 (Div. 3)") 228 229 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution** 236 237 ``` 238 #include <bits/stdc++.h> 239 #include <ext/pb_ds/assoc_container.hpp> 240 241 using namespace std; 242 using namespace __gnu_pbds; 243 244 typedef pair<int, int> node; 245 typedef tree<node, null_type, less<node>, 246 rb_tree_tag, tree_order_statistics_node_update> ordered_set; 247 248 int main() { 249 int t; 250 cin >> t; 251 while (t--) { 252 int n; 253 cin >> n; 254 ordered_set s; 255 long long cnt = 0; 256 for (int i = 0; i < n; i++) { 257 int a; 258 cin >> a; 259 int less = s.order_of_key(node(a, 0)), 260 greater = i - s.order_of_key(node(a, n)); 261 cnt += min(less, greater); 262 s.insert(node(a, i)); 263 } 264 cout << cnt << '\n'; 265 } 266 } 267 ``` 268 269 [1579F - Array Stabilization (AND version)](/contest/1579/problem/F "Codeforces Round 744 (Div. 3)") 270 271 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 272 273 **Tutorial** 274 275 Tutorial is loading... 276 277 **Solution** 278 279 ``` 280 #include <bits/stdc++.h> 281 282 using namespace std; 283 284 int main() { 285 int t; 286 cin >> t; 287 while (t--) { 288 int n, d; 289 cin >> n >> d; 290 vector<int> a(n); 291 for (int i = 0; i < n; i++) 292 cin >> a[i]; 293 vector<bool> used(n, false); 294 bool fail = false; 295 int res = 0; 296 for (int i = 0; i < n; i++) { 297 if (used[i]) 298 continue; 299 int cur = i, pref = 0, last = 0, iter = 0, ans = 0; 300 do { 301 used[cur] = true; 302 if (a[cur] == 0) { 303 ans = max(ans, last); 304 last = 0; 305 } else { 306 last++; 307 if (iter == pref) { 308 pref++; 309 } 310 } 311 cur = (cur + d) % n; 312 iter++; 313 } while (cur != i); 314 if (iter != pref) 315 ans = max(ans, pref + last); 316 else { 317 fail = true; 318 break; 319 } 320 res = max(res, ans); 321 } 322 if (fail) 323 cout << "-1\n"; 324 else 325 cout << res << '\n'; 326 } 327 } 328 ``` 329 330 [1579G - Minimal Coverage](/contest/1579/problem/G "Codeforces Round 744 (Div. 3)") 331 332 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 333 334 **Tutorial** 335 336 Tutorial is loading... 337 338 **Solution** 339 340 ``` 341 #include <bits/stdc++.h> 342 343 using namespace std; 344 345 const int INF = 1000000000; 346 347 int main() { 348 int t; 349 cin >> t; 350 while (t--) { 351 int n; 352 cin >> n; 353 vector<int> a(n); 354 int maxl = 0; 355 for (int i = 0; i < n; i++) { 356 cin >> a[i]; 357 maxl = max(maxl, a[i]); 358 } 359 vector<vector<int>> dp(n + 1, vector<int>(2 * maxl + 1, INF)); 360 dp[0][0] = 0; 361 for (int i = 0; i < n; i++) { 362 for (int left = 0; left <= 2 * maxl; left++) { 363 if (dp[i][left] == INF) 364 continue; 365 dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]); 366 if (left + a[i] < dp[i + 1].size()) { 367 dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0)); 368 } 369 } 370 } 371 372 int ans = 2 * maxl + 1; 373 for (int left = 0; left <= 2 * maxl; left++) 374 ans = min(ans, left + dp[n][left]); 375 cout << ans << '\n'; 376 } 377 } 378 ```