1028.md (16178B)
1 Source: https://codeforces.com/blog/entry/61493 2 3 Thanks [bmerry](/profile/bmerry "Legendary Grandmaster bmerry") for posting his solutions, we gently took some of them as a base for editorial. 4 5 Tutorial is loading... 6 7 Problem author: [VadymKa](/profile/VadymKa "Expert VadymKa") 8 9 Problem developers: [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [malcolm](/profile/malcolm "Master malcolm") 10 11 **Code** 12 13 ``` 14 static class SquareInside { 15 final int inf = (int) 1e9; 16 17 public void solve(int testNumber, InputReader in, PrintWriter out) { 18 int n = in.readInt(), m = in.readInt(); 19 char[][] s = new char[n][]; 20 for (int i = 0; i < n; i++) { 21 s[i] = in.readWord().toCharArray(); 22 } 23 int minX = inf, maxX = -inf, minY = inf, maxY = -inf; 24 for (int i = 0; i < n; i++) { 25 for (int j = 0; j < m; j++) { 26 if (s[i][j] == 'B') { 27 minX = Math.min(minX, i); 28 minY = Math.min(minY, j); 29 maxX = Math.max(maxX, i); 30 maxY = Math.max(maxY, j); 31 } 32 } 33 } 34 out.print((minX + maxX) / 2 + 1); 35 out.print(' '); 36 out.println((minY + maxY) / 2 + 1); 37 } 38 39 } 40 ``` 41 42 Tutorial is loading... 43 44 Problem author: [VadymKa](/profile/VadymKa "Expert VadymKa") 45 46 Problem developers: [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [malcolm](/profile/malcolm "Master malcolm"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [Errichto](/profile/Errichto "International Grandmaster Errichto") 47 48 **Code** 49 50 ``` 51 int len = 400; 52 cout << string(len, '5') << "\n"; 53 cout << (string(len - 1, '4') + '5') << "\n"; 54 ``` 55 56 Tutorial is loading... 57 58 Problem author: [malcolm](/profile/malcolm "Master malcolm") 59 60 Problem developers: [yarrr](/profile/yarrr "Candidate Master yarrr"), [Edvard](/profile/Edvard "Candidate Master Edvard"), [malcolm](/profile/malcolm "Master malcolm"), [Errichto](/profile/Errichto "International Grandmaster Errichto") 61 62 **Code** 63 64 ``` 65 static class Rectangle { 66 public Point topLeft, bottomRight; 67 68 public Rectangle(Point topLeft, Point bottomRight) { 69 this.topLeft = topLeft; 70 this.bottomRight = bottomRight; 71 } 72 73 public Rectangle intersect(Rectangle other) { 74 if (other == null) { 75 return null; 76 } 77 int x0 = Math.max(topLeft.x, other.topLeft.x); 78 int y0 = Math.max(topLeft.y, other.topLeft.y); 79 int x1 = Math.min(bottomRight.x, other.bottomRight.x); 80 int y1 = Math.min(bottomRight.y, other.bottomRight.y); 81 if (x0 > x1 || y0 > y1) { 82 return null; 83 } 84 return new Rectangle(new Point(x0, y0), new Point(x1, y1)); 85 } 86 } 87 88 private void solve() throws IOException { 89 int rectanglesCount = nextInt(); 90 Rectangle[] rectangles = new Rectangle[rectanglesCount]; 91 for (int i = 0; i < rectanglesCount; i++) { 92 Point topLeft = new Point(nextInt(), nextInt()); 93 Point bottomRight = new Point(nextInt(), nextInt()); 94 rectangles[i] = new Rectangle(topLeft, bottomRight); 95 } 96 Rectangle[] prefixIntersection = new Rectangle[rectanglesCount + 1]; 97 Rectangle[] suffixIntersection = new Rectangle[rectanglesCount + 1]; 98 prefixIntersection[0] = suffixIntersection[0] = new Rectangle( 99 new Point(Integer.MIN_VALUE, Integer.MIN_VALUE), 100 new Point(Integer.MAX_VALUE, Integer.MAX_VALUE) 101 ); 102 for (int i = 1; i <= rectanglesCount; i++) { 103 prefixIntersection[i] = rectangles[i - 1].intersect(prefixIntersection[i - 1]); 104 suffixIntersection[i] = rectangles[rectanglesCount - i].intersect(suffixIntersection[i - 1]); 105 } 106 107 for (int i = 0; i <= rectanglesCount; i++) { 108 if (prefixIntersection[i] != null) { 109 Rectangle intersection = prefixIntersection[i].intersect(suffixIntersection[rectanglesCount - i - 1]); 110 if (intersection != null) { 111 out.println(intersection.topLeft); 112 return; 113 } 114 } 115 } 116 throw new AssertionError(); 117 } 118 ``` 119 120 **Bonus:** Solve the problem, if you need to find intersection of some *n* - *k* of *n* rectangles, if *k* ≤ 10. Without data structures. 121 122 Tutorial is loading... 123 124 Problem author: [Errichto](/profile/Errichto "International Grandmaster Errichto") 125 126 Problem developers: [zemen](/profile/zemen "International Grandmaster zemen"), [Errichto](/profile/Errichto "International Grandmaster Errichto"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw") 127 128 **Code** 129 130 ``` 131 #include <bits/stdc++.h> 132 using namespace std; 133 using ll = long long; 134 using ld = long double; 135 136 const int mod = 1e9 + 7; 137 138 signed main() { 139 #ifdef LOCAL 140 assert(freopen("test.in", "r", stdin)); 141 #endif 142 int n; 143 cin >> n; 144 map<int, int> a{{INT_MIN, 1}, {INT_MAX, 0}}; 145 set<int*> non0{&a.begin()->second}; 146 for (int i = 0; i < n; ++i) { 147 string t; 148 int x; 149 cin >> t >> x; 150 if (t == "ADD") { 151 auto it = a.lower_bound(x); 152 assert(it != a.begin()); 153 --it; 154 int ways = it->second; 155 auto m = a.emplace(x, ways).first; 156 non0.insert(&m->second); 157 } else { 158 auto m = a.find(x); 159 assert(m != a.end() && m != a.begin()); 160 auto it = prev(m); 161 auto& w = it->second; 162 w = (w + m->second) % mod; 163 non0.insert(&it->second); 164 non0.erase(&m->second); 165 a.erase(m); 166 for (auto it2 = non0.begin(); it2 != non0.end(); ) { 167 if (*it2 == &it->second) { 168 ++it2; 169 } else { 170 *(*it2) = 0; 171 it2 = non0.erase(it2); 172 } 173 } 174 } 175 } 176 int res = 0; 177 for (auto p : a) { 178 res = (res + p.second) % mod; 179 } 180 cout << res << '\n'; 181 } 182 ``` 183 184 Tutorial is loading... 185 186 Problem author: [zemen](/profile/zemen "International Grandmaster zemen") 187 188 Problem developers: [yarrr](/profile/yarrr "Candidate Master yarrr"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma") 189 190 **Code** 191 192 ``` 193 void solve(__attribute__((unused)) bool read) { 194 int n; 195 cin >> n; 196 vector<int> b(n, 0); 197 for (int i = 0; i < n; ++i) { 198 cin >> b[i]; 199 } 200 int mx = *max_element(all(b)); 201 int start_pos = -1; 202 for (int i = 0; i < n; ++i) { 203 if (b[i] == mx && b[(i - 1 + n) % n] != mx) { 204 start_pos = i; 205 break; 206 } 207 } 208 if (start_pos == -1) { 209 if (mx == 0) { 210 cout << "YES\n"; 211 for (int i = 0; i < n; ++i) { 212 cout << 1 << " \n"[i + 1 == n]; 213 } 214 return; 215 } 216 cout << "NO\n"; 217 return; 218 } 219 auto a = b; 220 for (int i = 1; i < n; ++i) { 221 int pos = (start_pos - i + n) % n, prev_pos = (start_pos + 1 - i + n) % n; 222 a[pos] += a[prev_pos]; 223 if (i == 1) { 224 a[pos] += mx; 225 } 226 } 227 cout << "YES\n"; 228 for (int x : a) { 229 cout << x << " "; 230 } 231 cout << "\n"; 232 233 } 234 ``` 235 236 Tutorial is loading... 237 238 Problem author: [Errichto](/profile/Errichto "International Grandmaster Errichto") 239 240 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [malcolm](/profile/malcolm "Master malcolm") 241 242 **Code** 243 244 ``` 245 struct Point { 246 int x, y; 247 Point() {} 248 Point(int x, int y) : x(x), y(y) {} 249 void scan() { 250 cin >> x >> y; 251 } 252 auto key() const { 253 return make_pair(x, y); 254 } 255 bool operator < (const Point& ot) const { 256 return key() < ot.key(); 257 } 258 bool operator == (const Point& ot) const { 259 return key() == ot.key(); 260 } 261 Point operator + (const Point& ot) const { 262 return Point(x + ot.x, y + ot.y); 263 } 264 li sqr_dist() { 265 return x * 1LL * x + y * 1LL * y; 266 } 267 void normalize() { 268 auto g = gcd(x, y); 269 x /= g; 270 y /= g; 271 } 272 }; 273 274 struct Hasher { 275 size_t operator () (const Point& pt) const { 276 return pt.x * 2352345 + pt.y; 277 } 278 }; 279 280 enum Type { 281 INSERT = 1, 282 REMOVE = 2, 283 QUERY = 3 284 }; 285 286 struct Query { 287 Type type; 288 Point pt; 289 int dist_id; 290 void scan() { 291 int type1; 292 cin >> type1; 293 type = Type(type1); 294 pt.scan(); 295 } 296 }; 297 298 void solve(__attribute__((unused)) bool read) { 299 int Q; 300 cin >> Q; 301 vector<Query> queries(Q); 302 map<li, vector<Point>> all_points; 303 vector<li> dists; 304 set<Point> have; 305 for (int i = 0; i < Q; ++i) { 306 queries[i].scan(); 307 auto& pt = queries[i].pt; 308 if (queries[i].type != QUERY) { 309 all_points[pt.sqr_dist()].push_back(pt); 310 dists.push_back(pt.sqr_dist()); 311 } else { 312 pt.normalize(); 313 } 314 } 315 make_unique(dists); 316 for (auto& q : queries) { 317 q.dist_id = (int)(lower_bound(all(dists), q.pt.sqr_dist()) - dists.begin()); 318 } 319 vector<vector<char>> has_point(dists.size()); 320 vector<vector<Point>> points_by_dist_id(dists.size()); 321 vector<vector<vector<Point>>> sum_points(dists.size()); 322 unordered_map<Point, pair<int, int>, Hasher> point_position; 323 for (auto& item : all_points) { 324 make_unique(item.second); 325 int dist_id = (int)(lower_bound(all(dists), item.first) - dists.begin()); 326 has_point[dist_id].assign(item.second.size(), false); 327 points_by_dist_id[dist_id] = item.second; 328 sum_points[dist_id].assign(item.second.size(), vector<Point>(item.second.size())); 329 for (int i = 0; i < item.second.size(); ++i) { 330 point_position[item.second[i]] = {dist_id, i}; 331 for (int j = 0; j < item.second.size(); ++j) { 332 sum_points[dist_id][i][j] = item.second[i] + item.second[j]; 333 sum_points[dist_id][i][j].normalize(); 334 } 335 } 336 } 337 unordered_map<Point, int, Hasher> on_line; 338 unordered_map<Point, int, Hasher> good_pairs; 339 340 auto change_on_line = [&] (Point pt, bool add) { 341 pt.normalize(); 342 if (add) { 343 ++on_line[pt]; 344 } else { 345 assert(on_line[pt] > 0); 346 --on_line[pt]; 347 } 348 }; 349 350 int n_points = 0; 351 for (auto& cur_q : queries) { 352 auto& pt = cur_q.pt; 353 int dist_id = cur_q.dist_id; 354 if (cur_q.type == INSERT) { 355 ++n_points; 356 int pos = point_position[pt].second; 357 assert(!has_point[dist_id][pos]); 358 change_on_line(pt, true); 359 for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) { 360 if (i == pos || !has_point[dist_id][i]) { 361 continue; 362 } 363 ++good_pairs[sum_points[dist_id][i][pos]]; 364 } 365 has_point[dist_id][pos] = true; 366 } else if (cur_q.type == REMOVE) { 367 --n_points; 368 int pos = point_position[pt].second; 369 assert(has_point[dist_id][pos]); 370 change_on_line(pt, false); 371 for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) { 372 if (i == pos || !has_point[dist_id][i]) { 373 continue; 374 } 375 --good_pairs[sum_points[dist_id][i][pos]]; 376 } 377 has_point[dist_id][pos] = false; 378 } else if (cur_q.type == QUERY) { 379 pt.normalize(); 380 cout << n_points - 2 * good_pairs[pt] - on_line[pt] << "\n"; 381 } 382 } 383 384 } 385 ``` 386 387 Tutorial is loading... 388 389 Problem author: [zeliboba](/profile/zeliboba "Grandmaster zeliboba") 390 391 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw") 392 393 **Code** 394 395 ``` 396 private static final int MAX_WIDTH = 10000; 397 private static final int QUERIES = 5; 398 public static final long INF = 20000000000000000L; 399 long[][] memo = new long[QUERIES + 1][MAX_WIDTH + 1]; 400 401 long dp(int guesses, long l) { 402 if (guesses == 0) { 403 return l; 404 } 405 if (l > MAX_WIDTH) { 406 return Math.min(INF, dp(guesses, MAX_WIDTH) + l - MAX_WIDTH); 407 } 408 409 if (memo[guesses][(int) l] != 0) { 410 return memo[guesses][(int) l]; 411 } 412 long ans = l; 413 for (int i = 0; i < l; ++i) { 414 ans = dp(guesses - 1, ans); 415 ++ans; 416 } 417 ans = dp(guesses - 1, ans); 418 return memo[guesses][(int) l] = Math.min(ans, INF); 419 } 420 private void run() throws IOException { 421 long l = 1; 422 long r = dp(QUERIES, 1); 423 for (int queriesNext = QUERIES - 1; queriesNext >= 0; --queriesNext) { 424 List<Long> query = new ArrayList<>(); 425 long curL = l; 426 for (int i = 0, e = (int)Math.min(l, MAX_WIDTH); i < e; ++i) { 427 long end = dp(queriesNext, curL); 428 query.add(end); 429 curL = end + 1; 430 } 431 assert r == dp(queriesNext, curL); 432 out.print(query.size()); 433 for (long x: query) { 434 out.print(" "); 435 out.print(x); 436 } 437 out.println(); 438 out.flush(); 439 System.out.flush(); 440 441 int ans = readInt(); 442 if (ans < 0) { 443 return; 444 } 445 if (ans > 0) { 446 l = query.get(ans - 1) + 1; 447 } 448 if (ans != query.size()) { 449 r = query.get(ans); 450 } 451 452 assert dp(queriesNext, l) == r; 453 } 454 } 455 ``` 456 457 Tutorial is loading... 458 459 Problem author: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma") 460 461 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [gchebanov](/profile/gchebanov "International Master gchebanov"), [malcolm](/profile/malcolm "Master malcolm") 462 463 **Code** 464 465 ``` 466 const int C = 5032107 + 1; 467 int lp[C]; 468 int fred[C]; 469 int num_primes[C]; 470 471 const int MAX_DIVISORS = 7; 472 const int MAX_ANS = 2 * MAX_DIVISORS; 473 474 int max_left[MAX_DIVISORS + 1][C]; 475 int max_border[MAX_ANS + 1]; 476 477 vector<int> cur_primes; 478 479 vector<int> divs; 480 481 void get_divisors(int n) { 482 divs = {1}; 483 while (n > 1) { 484 int p = lp[n]; 485 n /= p; 486 int sz = divs.size(); 487 for (int i = 0; i < sz; ++i) { 488 divs.push_back(divs[i] * p); 489 } 490 } 491 } 492 493 void solve(bool read) { 494 vector<int> pr; 495 for (int i = 2; i < C; ++i) { 496 if (lp[i] == 0) { 497 lp[i] = i; 498 pr.push_back(i); 499 } 500 for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < C; ++j) { 501 lp[i * pr[j]] = pr[j]; 502 } 503 } 504 fred[1] = 1; 505 for (int i = 2; i < C; ++i) { 506 int p = lp[i]; 507 int cur = i / p; 508 if (cur % p == 0) { 509 fred[i] = fred[cur / p]; 510 num_primes[i] = num_primes[cur / p]; 511 } else { 512 fred[i] = p * fred[cur]; 513 num_primes[i] = num_primes[cur] + 1; 514 } 515 } 516 517 for (int i = 0; i < C; ++i) { 518 for (int j = 0; j <= MAX_DIVISORS; ++j) { 519 max_left[j][i] = -1; 520 } 521 } 522 memset(max_border, -1, sizeof(max_border)); 523 524 int n; 525 cin >> n; 526 int Q; 527 cin >> Q; 528 vector<int> a(n); 529 for (int i = 0; i < n; ++i) { 530 cin >> a[i]; 531 a[i] = fred[a[i]]; 532 } 533 534 vector<vector<pair<int, int>>> queries(n); 535 536 vector<int> res(Q); 537 for (int i = 0; i < Q; ++i) { 538 int l, r; 539 cin >> l >> r; 540 --l; --r; 541 queries[r].push_back({l, i}); 542 } 543 544 for (int i = 0; i < n; ++i) { 545 get_divisors(a[i]); 546 for (int d : divs) { 547 int first_add = num_primes[a[i]] - num_primes[d]; 548 for (int prev_ans = 0; prev_ans <= MAX_DIVISORS; ++prev_ans) { 549 int cur_left = max_left[prev_ans][d]; 550 int cur_ans = first_add + prev_ans; 551 if (cur_ans <= MAX_ANS) { 552 relax_max(max_border[cur_ans], cur_left); 553 } 554 } 555 } 556 for (int d : divs) { 557 int first_add = num_primes[a[i]] - num_primes[d]; 558 relax_max(max_left[first_add][d], i); 559 } 560 for (auto q : queries[i]) { 561 res[q.second] = MAX_ANS + 1; 562 for (int cur_ans = 0; cur_ans <= MAX_ANS; ++cur_ans) { 563 if (max_border[cur_ans] >= q.first) { 564 res[q.second] = cur_ans; 565 break; 566 } 567 } 568 assert(res[q.second] <= MAX_ANS); 569 } 570 } 571 572 int sum_ans = 0; 573 for (int i = 0; i < Q; ++i) { 574 cout << res[i] << '\n'; 575 } 576 } 577 ```