1971.md (9988B)
1 Source: https://codeforces.com/blog/entry/129364 2 3 Thank you for participating! 4 5 [1971A - My First Sorting Problem](/contest/1971/problem/A "Codeforces Round 944 (Div. 4)") 6 7 Idea: [flamestorm](/profile/flamestorm "Master flamestorm") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const int MAX = 200'007; 21 const int MOD = 1'000'000'007; 22 23 void solve() { 24 int x, y; 25 cin >> x >> y; 26 cout << min(x, y) << ' ' << max(x, y) << '\n'; 27 } 28 29 int main() { 30 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 31 // solve(); 32 } 33 ``` 34 35 [1971B - Different String](/contest/1971/problem/B "Codeforces Round 944 (Div. 4)") 36 37 Idea: [flamestorm](/profile/flamestorm "Master flamestorm") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 const int MAX = 200'007; 51 const int MOD = 1'000'000'007; 52 53 void solve() { 54 string s; 55 cin >> s; 56 bool ok = false; 57 for (int i = 1; i < (int)(s.length()); i++) { 58 if (s[i] != s[0]) {swap(s[i], s[0]); ok = true; break;} 59 } 60 if (!ok) { 61 cout << "NO\n"; return; 62 } 63 cout << "YES\n"; 64 cout << s << '\n'; 65 } 66 67 int main() { 68 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 69 // solve(); 70 } 71 ``` 72 73 [1971C - Clock and Strings](/contest/1971/problem/C "Codeforces Round 944 (Div. 4)") 74 75 Idea: [flamestorm](/profile/flamestorm "Master flamestorm") 76 77 **Tutorial** 78 79 Tutorial is loading... 80 81 **Solution** 82 83 ``` 84 #include <bits/stdc++.h> 85 86 using namespace std; 87 88 const int MAX = 200'007; 89 const int MOD = 1'000'000'007; 90 91 void solve() { 92 int a, b, c, d; 93 cin >> a >> b >> c >> d; 94 string s; 95 for (int i = 1; i <= 12; i++) { 96 if (i == a || i == b) {s += "a";} 97 if (i == c || i == d) {s += "b";} 98 } 99 cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n"); 100 } 101 102 int main() { 103 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 104 // solve(); 105 } 106 ``` 107 108 [1971D - Binary Cut](/contest/1971/problem/D "Codeforces Round 944 (Div. 4)") 109 110 Idea: [flamestorm](/profile/flamestorm "Master flamestorm") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Solution** 117 118 ``` 119 #include <bits/stdc++.h> 120 121 using namespace std; 122 123 const int MAX = 200'007; 124 const int MOD = 1'000'000'007; 125 126 void solve() { 127 string s; 128 cin >> s; 129 int res = 1; 130 bool ex = false; 131 for (int i = 0; i + 1 < (int)(s.size()); i++) { 132 res += (s[i] != s[i + 1]); 133 ex |= (s[i] == '0' && s[i + 1] == '1'); 134 } 135 cout << res - ex << '\n'; 136 } 137 138 int main() { 139 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 140 // solve(); 141 } 142 ``` 143 144 [1971E - Find the Car](/contest/1971/problem/E "Codeforces Round 944 (Div. 4)") 145 146 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 147 148 **Tutorial** 149 150 Tutorial is loading... 151 152 **Solution** 153 154 ``` 155 #include <iostream> 156 #include <algorithm> 157 #include <vector> 158 #include <array> 159 #include <set> 160 #include <map> 161 #include <queue> 162 #include <stack> 163 #include <list> 164 #include <chrono> 165 #include <random> 166 #include <cstdlib> 167 #include <cmath> 168 #include <ctime> 169 #include <cstring> 170 #include <iomanip> 171 #include <bitset> 172 #include <cassert> 173 typedef long long ll; 174 using namespace std; 175 176 void solve() 177 { 178 int n, k, q; 179 cin >> n >> k >> q; 180 vector<long long> a(k+1), b(k+1); 181 a[0] = 0; 182 b[0] = 0; 183 for(int i = 1; i <= k; i++) 184 { 185 cin >> a[i]; 186 } 187 for(int i = 1; i <= k; i++) 188 { 189 cin >> b[i]; 190 } 191 for(int i = 0; i < q; i++) 192 { 193 long long c; 194 cin >> c; 195 int l = 0, r = k; 196 while(l <= r) 197 { 198 int mid = l+r>>1; 199 if(a[mid] > c) 200 { 201 r = mid-1; 202 } 203 else 204 { 205 l = mid+1; 206 } 207 } 208 if(a[r] == c) 209 { 210 cout << b[r] << " "; 211 continue; 212 } 213 long long ans = b[r] + (c-a[r])*(b[r+1]-b[r])/(a[r+1]-a[r]); 214 cout << ans << " "; 215 } 216 cout << endl; 217 } 218 219 int32_t main(){ 220 int t = 1; 221 cin >> t; 222 while (t--) { 223 solve(); 224 } 225 } 226 ``` 227 228 [1971F - Circle Perimeter](/contest/1971/problem/F "Codeforces Round 944 (Div. 4)") 229 230 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 231 232 **Tutorial** 233 234 Tutorial is loading... 235 236 **Solution** 237 238 ``` 239 #include <iostream> 240 using namespace std; 241 242 void solve() 243 { 244 long long r; 245 cin >> r; 246 long long height = r; 247 long long ans = 0; 248 for(long long i = 0; i <= r; i++) 249 { 250 while(i*i+height*height >= (r+1)*(r+1)) 251 { 252 height--; 253 } 254 long long cop = height; 255 while(i*i+cop*cop >= r*r && cop > 0) 256 { 257 cop--; 258 ans++; 259 } 260 } 261 cout << ans*4 << endl; 262 } 263 264 int32_t main(){ 265 int t = 1; 266 cin >> t; 267 while (t--) { 268 solve(); 269 } 270 } 271 ``` 272 273 [1971G - XOUR](/contest/1971/problem/G "Codeforces Round 944 (Div. 4)") 274 275 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 276 277 **Tutorial** 278 279 Tutorial is loading... 280 281 **Solution** 282 283 ``` 284 #include <iostream> 285 #include <algorithm> 286 #include <vector> 287 #include <map> 288 #include <queue> 289 290 using namespace std; 291 292 293 void solve() 294 { 295 int n; 296 cin >> n; 297 vector<int> a(n); 298 map<int, priority_queue<int>> mp; 299 for(int i = 0; i < n; i++) 300 { 301 cin >> a[i]; 302 mp[a[i]>>2].push(-a[i]); 303 } 304 for(int i = 0; i < n; i++) 305 { 306 cout << -mp[a[i]>>2].top() << " "; 307 mp[a[i]>>2].pop(); 308 } 309 cout << endl; 310 } 311 312 int32_t main(){ 313 int t = 1; 314 cin >> t; 315 while (t--) { 316 solve(); 317 } 318 } 319 ``` 320 321 [1971H - ±1](/contest/1971/problem/H "Codeforces Round 944 (Div. 4)") 322 323 Idea: [flamestorm](/profile/flamestorm "Master flamestorm") 324 325 **Tutorial** 326 327 Tutorial is loading... 328 329 **Solution** 330 331 ``` 332 #include <bits/stdc++.h> 333 334 335 #include <algorithm> 336 #include <utility> 337 #include <vector> 338 339 namespace atcoder { 340 namespace internal { 341 342 template <class E> struct csr { 343 std::vector<int> start; 344 std::vector<E> elist; 345 csr(int n, const std::vector<std::pair<int, E>>& edges) 346 : start(n + 1), elist(edges.size()) { 347 for (auto e : edges) { 348 start[e.first + 1]++; 349 } 350 for (int i = 1; i <= n; i++) { 351 start[i] += start[i - 1]; 352 } 353 auto counter = start; 354 for (auto e : edges) { 355 elist[counter[e.first]++] = e.second; 356 } 357 } 358 }; 359 360 // Reference: 361 // R. Tarjan, 362 // Depth-First Search and Linear Graph Algorithms 363 struct scc_graph { 364 public: 365 scc_graph(int n) : _n(n) {} 366 367 int num_vertices() { return _n; } 368 369 void add_edge(int from, int to) { edges.push_back({from, {to}}); } 370 371 // @return pair of (# of scc, scc id) 372 std::pair<int, std::vector<int>> scc_ids() { 373 auto g = csr<edge>(_n, edges); 374 int now_ord = 0, group_num = 0; 375 std::vector<int> visited, low(_n), ord(_n, -1), ids(_n); 376 visited.reserve(_n); 377 auto dfs = [&](auto self, int v) -> void { 378 low[v] = ord[v] = now_ord++; 379 visited.push_back(v); 380 for (int i = g.start[v]; i < g.start[v + 1]; i++) { 381 auto to = g.elist[i].to; 382 if (ord[to] == -1) { 383 self(self, to); 384 low[v] = std::min(low[v], low[to]); 385 } else { 386 low[v] = std::min(low[v], ord[to]); 387 } 388 } 389 if (low[v] == ord[v]) { 390 while (true) { 391 int u = visited.back(); 392 visited.pop_back(); 393 ord[u] = _n; 394 ids[u] = group_num; 395 if (u == v) break; 396 } 397 group_num++; 398 } 399 }; 400 for (int i = 0; i < _n; i++) { 401 if (ord[i] == -1) dfs(dfs, i); 402 } 403 for (auto& x : ids) { 404 x = group_num - 1 - x; 405 } 406 return {group_num, ids}; 407 } 408 409 std::vector<std::vector<int>> scc() { 410 auto ids = scc_ids(); 411 int group_num = ids.first; 412 std::vector<int> counts(group_num); 413 for (auto x : ids.second) counts[x]++; 414 std::vector<std::vector<int>> groups(ids.first); 415 for (int i = 0; i < group_num; i++) { 416 groups[i].reserve(counts[i]); 417 } 418 for (int i = 0; i < _n; i++) { 419 groups[ids.second[i]].push_back(i); 420 } 421 return groups; 422 } 423 424 private: 425 int _n; 426 struct edge { 427 int to; 428 }; 429 std::vector<std::pair<int, edge>> edges; 430 }; 431 432 } // namespace internal 433 434 } // namespace atcoder 435 436 #include <cassert> 437 #include <vector> 438 439 namespace atcoder { 440 441 // Reference: 442 // B. Aspvall, M. Plass, and R. Tarjan, 443 // A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean 444 // Formulas 445 struct two_sat { 446 public: 447 two_sat() : _n(0), scc(0) {} 448 two_sat(int n) : _n(n), _answer(n), scc(2 * n) {} 449 450 void add_clause(int i, bool f, int j, bool g) { 451 assert(0 <= i && i < _n); 452 assert(0 <= j && j < _n); 453 scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0)); 454 scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0)); 455 } 456 bool satisfiable() { 457 auto id = scc.scc_ids().second; 458 for (int i = 0; i < _n; i++) { 459 if (id[2 * i] == id[2 * i + 1]) return false; 460 _answer[i] = id[2 * i] < id[2 * i + 1]; 461 } 462 return true; 463 } 464 std::vector<bool> answer() { return _answer; } 465 466 private: 467 int _n; 468 std::vector<bool> _answer; 469 internal::scc_graph scc; 470 }; 471 472 } // namespace atcoder 473 474 475 using namespace std; 476 using namespace atcoder; 477 478 void solve() { 479 int n; 480 cin >> n; 481 int b[3][n]; 482 for (int i = 0; i < 3; i++) { 483 for (int j = 0; j < n; j++) { 484 cin >> b[i][j]; 485 } 486 } 487 two_sat ts(n); 488 for (int j = 0; j < n; j++) { 489 for (int i = 0; i < 3; i++) { 490 int nxt = (i + 1) % 3; 491 ts.add_clause(abs(b[i][j]) - 1, b[i][j] > 0, abs(b[nxt][j]) - 1, b[nxt][j] > 0); 492 } 493 } 494 cout << (ts.satisfiable() ? "YES\n" : "NO\n"); 495 } 496 497 int main() { 498 ios::sync_with_stdio(false); 499 cin.tie(nullptr); 500 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 501 // solve(); 502 } 503 ```