1547.md (8615B)
1 Source: https://codeforces.com/blog/entry/92715 2 3 [1547A - Shortest Path with Obstacle](/contest/1547/problem/A "Codeforces Round 731 (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 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 20 int main() { 21 int t; 22 cin >> t; 23 forn(tt, t) { 24 vector<int> a(2), b(2), f(2); 25 cin >> a[0] >> a[1]; 26 cin >> b[0] >> b[1]; 27 cin >> f[0] >> f[1]; 28 int ans = abs(a[0] - b[0]) + abs(a[1] - b[1]); 29 if ((a[0] == b[0] && a[0] == f[0] && min(a[1], b[1]) < f[1] && f[1] < max(a[1], b[1])) 30 || (a[1] == b[1] && a[1] == f[1] && min(a[0], b[0]) < f[0] && f[0] < max(a[0], b[0]))) 31 ans += 2; 32 cout << ans << endl; 33 } 34 } 35 ``` 36 37 [1547B - Alphabetical Strings](/contest/1547/problem/B "Codeforces Round 731 (Div. 3)") 38 39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 #define forn(i, n) for (int i = 0; i < int(n); i++) 53 54 int main() { 55 int t; 56 cin >> t; 57 forn(tt, t) { 58 string s; 59 cin >> s; 60 size_t L = s.find('a'); 61 if (L == string::npos) { 62 cout << "NO" << endl; 63 continue; 64 } 65 size_t n = s.length(), R = L; 66 bool yes = true; 67 for (size_t i = 1; i < n; i++) { 68 size_t pos = s.find(char('a' + i)); 69 if (pos == string::npos || (pos != L - 1 && pos != R + 1)) { 70 yes = false; 71 break; 72 } else { 73 L = min(L, pos); 74 R = max(R, pos); 75 } 76 } 77 cout << (yes ? "YES" : "NO") << endl; 78 } 79 } 80 ``` 81 82 [1547C - Pair Programming](/contest/1547/problem/C "Codeforces Round 731 (Div. 3)") 83 84 Idea: [geranazavr555](/profile/geranazavr555 "Headquarters, geranazavr555"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <iostream> 94 #include <vector> 95 96 typedef std::vector<int> vi; 97 98 int main() { 99 int t; 100 std::cin >> t; 101 while (t--) { 102 int k, n, m; 103 std::cin >> k >> n >> m; 104 105 vi a(n), b(m); 106 for (int i = 0; i < n; i++) 107 std::cin >> a[i]; 108 for (int i = 0; i < m; i++) 109 std::cin >> b[i]; 110 111 int pos1 = 0, pos2 = 0; 112 vi res; 113 bool ok = true; 114 while (pos1 != n || pos2 != m) { 115 if (pos1 != n && a[pos1] == 0) { 116 res.push_back(0); 117 k++; 118 pos1++; 119 } else if (pos2 != m && b[pos2] == 0) { 120 res.push_back(0); 121 k++; 122 pos2++; 123 } else if (pos1 != n && a[pos1] <= k) { 124 res.push_back(a[pos1++]); 125 } else if (pos2 != m && b[pos2] <= k) { 126 res.push_back(b[pos2++]); 127 } else { 128 std::cout << -1 << '\n'; 129 ok = false; 130 break; 131 } 132 } 133 134 if (ok) { 135 for (int cur : res) 136 std::cout << cur << ' '; 137 std::cout << std::endl; 138 } 139 } 140 141 return 0; 142 } 143 ``` 144 145 [1547D - Co-growing Sequence](/contest/1547/problem/D "Codeforces Round 731 (Div. 3)") 146 147 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution** 154 155 ``` 156 def f(x, y): 157 return x & ~y 158 159 t = int(input()) 160 for tt in range(t): 161 n = int(input()) 162 a = list(map(int, input().split())) 163 164 ans = [0] * n 165 for i in range(1, n): 166 ans[i] = f(ans[i - 1] ^ a[i - 1], a[i]) 167 print(" ".join(map(str, ans))) 168 ``` 169 170 [1547E - Air Conditioners](/contest/1547/problem/E "Codeforces Round 731 (Div. 3)") 171 172 Idea: [geranazavr555](/profile/geranazavr555 "Headquarters, geranazavr555"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution** 179 180 ``` 181 #include <bits/stdc++.h> 182 183 using namespace std; 184 185 #define forn(i, n) for (int i = 0; i < int(n); i++) 186 187 int main() { 188 int t; 189 cin >> t; 190 forn(tt, t) { 191 int n, k; 192 cin >> n >> k; 193 vector<int> a(k); 194 forn(i, k) 195 cin >> a[i]; 196 vector<int> t(k); 197 forn(i, k) 198 cin >> t[i]; 199 vector<long long> c(n, INT_MAX); 200 forn(i, k) 201 c[a[i] - 1] = t[i]; 202 203 long long p; 204 205 vector<long long> L(n, INT_MAX); 206 p = INT_MAX; 207 forn(i, n) { 208 p = min(p + 1, c[i]); 209 L[i] = p; 210 } 211 212 vector<long long> R(n, INT_MAX); 213 p = INT_MAX; 214 for (int i = n - 1; i >= 0; i--) { 215 p = min(p + 1, c[i]); 216 R[i] = p; 217 } 218 219 forn(i, n) 220 cout << min(L[i], R[i]) << " "; 221 cout << endl; 222 } 223 } 224 ``` 225 226 [1547F - Array Stabilization (GCD version)](/contest/1547/problem/F "Codeforces Round 731 (Div. 3)") 227 228 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution** 235 236 ``` 237 #include <iostream> 238 #include <vector> 239 #include <set> 240 241 using namespace std; 242 243 const unsigned int MAX_A = 1'000'000; 244 vector<unsigned int> sieve(MAX_A + 1); 245 vector<unsigned int> prime; 246 247 unsigned int gcd(unsigned int a, unsigned int b) { 248 return b == 0 ? a : gcd(b, a % b); 249 } 250 251 unsigned int solve() { 252 253 unsigned int n; 254 cin >> n; 255 vector<unsigned int> a(n); 256 for (unsigned int i = 0; i < n; i++) { 257 cin >> a[i]; 258 } 259 260 unsigned int common = a[0]; 261 vector<set<unsigned int>> facts(n); 262 for (unsigned int i = 1; i < n; i++) { 263 common = gcd(common, a[i]); 264 } 265 for (unsigned int i = 0; i < n; i++) { 266 unsigned int t = a[i] / common; 267 while (t != 1) { 268 facts[i].insert(sieve[t]); 269 t /= sieve[t]; 270 } 271 } 272 273 unsigned int answer = 0; 274 for (unsigned int i = 0; i < n; i++) { 275 for (unsigned int p : facts[i]) { 276 int l = (i + n - 1) % n, r = i; 277 unsigned int cnt = 0; 278 while (facts[l].count(p) > 0) { 279 facts[l].erase(p); 280 l--; cnt++; 281 if (l < 0) { 282 l = n - 1; 283 } 284 } 285 while (facts[r].count(p) > 0) { 286 if (r != i) { 287 facts[r].erase(p); 288 } 289 ++r %= n; cnt++; 290 } 291 answer = max(answer, cnt); 292 } 293 facts[i].clear(); 294 } 295 296 return answer; 297 298 } 299 300 int main() { 301 302 sieve[1] = 1; 303 for (unsigned int i = 2; i <= MAX_A; i++) { 304 if (sieve[i] == 0) { 305 sieve[i] = i; 306 prime.push_back(i); 307 } 308 for (unsigned int j = 0; j < prime.size() && prime[j] <= sieve[i] && i * prime[j] <= MAX_A; j++) { 309 sieve[i * prime[j]] = prime[j]; 310 } 311 } 312 313 unsigned int t; 314 cin >> t; 315 for (unsigned int i = 0; i < t; i++) { 316 cout << solve() << '\n'; 317 } 318 319 } 320 ``` 321 322 [1547G - How Many Paths?](/contest/1547/problem/G "Codeforces Round 731 (Div. 3)") 323 324 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 325 326 **Tutorial** 327 328 Tutorial is loading... 329 330 **Solution** 331 332 ``` 333 #include <bits/stdc++.h> 334 335 using namespace std; 336 337 #define forn(i, n) for (int i = 0; i < int(n); i++) 338 339 int n; 340 vector<vector<int>> g; 341 set<int> s[2]; 342 343 void dfs(int u, vector<int>& color, bool use_s) { 344 color[u] = 1; 345 for (int v: g[u]) 346 if (color[v] == 0) 347 dfs(v, color, use_s); 348 else if (use_s) 349 s[color[v] - 1].insert(v); 350 color[u] = 2; 351 } 352 353 int main() { 354 int t; 355 cin >> t; 356 forn(tt, t) { 357 int m; 358 cin >> n >> m; 359 g = vector<vector<int>>(n); 360 forn(i, 2) 361 s[i] = set<int>(); 362 forn(i, m) { 363 int x, y; 364 cin >> x >> y; 365 x--, y--; 366 g[x].push_back(y); 367 } 368 vector<int> color = vector<int>(n); 369 dfs(0, color, true); 370 vector<vector<int>> c(2, vector<int>(n)); 371 forn(i, 2) 372 for (auto u: s[i]) 373 dfs(u, c[i], false); 374 forn(i, n) { 375 int ans = 0; 376 if (color[i] != 0) { 377 ans = 1; 378 if (c[0][i]) 379 ans = -1; 380 else if (c[1][i]) 381 ans = 2; 382 } 383 cout << ans << " "; 384 } 385 cout << endl; 386 } 387 } 388 ```