2046.md (48723B)
1 Source: https://codeforces.com/blog/entry/136908 2 3 ### Div2A 4 5 Alyona is happy when there are no unfinished layers — that is, in front of her is a perfect square with odd side length. Since the order of pieces is fixed, it is enough to keep track of the total current size $s$ of the puzzle, and after each day check, if the $s$ is a perfect square of an odd number. The easiest way to do that is to create an additional array containing $1^2, 3^2, 5^3, ..., 99^2$, and check after each day, whether $s$ is in this array. 6 7 **Code** 8 9 ``` 10 NT = int(input()) 11 12 sqs = set() 13 k = 1 14 while k * k <= 100 * 1000: 15 sqs.add(k * k) 16 k += 2 17 18 for T in range(NT): 19 n = int(input()) 20 a = list(map(int, input().split())) 21 answer = 0 22 cursum = 0 23 for t in a: 24 cursum += t 25 if cursum in sqs: 26 answer += 1 27 print(answer) 28 ``` 29 30 ### Div2B 31 32 Find the character which appears the lowest number of times — if tied, take the earlier character in the alphabet. Find the character which appears the highest number of times — if tied, take the later character in the alphabet. Then, replace any of the lowest-occurrence characters with the highest-occurrence character. 33 34 **Code** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 int main() { 42 cin.tie(0)->sync_with_stdio(0); 43 int t; 44 cin >> t; 45 while (t--) { 46 int n; 47 cin >> n; 48 string s; 49 cin >> s; 50 vector<int> occ(26); 51 for (int i=0; i<n; i++) 52 occ[s[i] - 'a'] += 1; 53 pair<pair<int,char>,int> low, high; 54 low = high = {{occ[s[0] - 'a'], s[0]}, 0}; 55 for (int i=1; i<n; i++) { 56 low = min(low, {{occ[s[i] - 'a'], s[i]}, i}); 57 high = max(high, {{occ[s[i] - 'a'], s[i]}, i}); 58 } 59 s[low.second] = s[high.second]; 60 cout << s << "\n"; 61 } 62 return 0; 63 } 64 ``` 65 66 ### Div2C 67 68 We can divide the columns in the matrix into three different groups: 69 70 1. the columns where we go through the top cell; 71 2. the columns where we go through the bottom cell; 72 3. the columns where we go through both cells. 73 74 There should be exactly one column in the $3$-rd group — this will be the column where we shift from the top row to the bottom row. However, all other columns can be redistributed between groups $1$ and $2$ as we want: if we want to put a column into the $1$-st group, we put it before the column where we go down; otherwise, we put it after the column where we go down. So, we can get any distribution of columns between the $1$-st and the $2$-nd group. 75 76 Now let's consider the contribution of each column to the answer. Columns from the $1$-st group add $a_{1,i}$ to the answer, columns from the $2$-nd group add $a_{2,i}$, the column from the $3$-rd group adds both of these values. So, we can iterate on the index of the column where we go down, take $a_{1,i} + a_{2,i}$ for it, and take $\max(a_{1,j}, a_{2,j})$ for every other column. This works in $O(n^2)$, and under the constraints of the problem, it is enough. 77 78 However, it is possible to solve the problem in $O(n)$. To do so, calculate the sum of $\max(a_{1,j}, a_{2,j})$ over all columns. Then, if we pick the $i$-th column as the column where we go down, the answer be equal to this sum, plus $\min(a_{1,i}, a_{2,i})$, since this will be the only column where we visit both cells. 79 80 **Code** 81 82 ``` 83 for _ in range(int(input())): 84 n = int(input()) 85 a = [] 86 for i in range(2): 87 a.append(list(map(int, input().split()))) 88 best = [max(a[0][i], a[1][i]) for i in range(n)] 89 full = [a[0][i] + a[1][i] for i in range(n)] 90 sum_best = sum(best) 91 ans = -10 ** 19 92 for i in range(n): 93 ans = max(ans, sum_best + full[i] - best[i]) 94 print(ans) 95 ``` 96 97 ### Div2D 98 99 The first idea is to notice, that each element is moved to the back at most once. Indeed, if we fix a subset of elements that we ever move to the back, we can perform the operation once on each of them in any order we like, and that becomes their final order with the smallest possible increase. The optimal order is, of course, the increasing order. The question is how to select this subset of elements to move to the back. 100 101 Since we need the lexicographically smallest array, we're looking for some greedy approach that chooses the smallest possible element on the next position one by one, left to right. 102 103 * What's the smallest number our resulting array can start with? Of course, the minimum. That means, all the elements in front of the minimum have to be moved to the back and be increased by one. 104 * What's the smallest number we can have on the second place, given that we have the minimum in the first positions? Either the smallest element to the right of the minimum, or the smallest element among those already moved to the back. 105 * ... 106 107 Analysing this approach, we see that as we go left to right, we keep picking elements from the suffix minima sequence, and keep growing the set of elements we have to move to the right to ''extract'' this sequence from the initial array. At one point, the next smallest element comes not from the suffix minima sequence, but from the pile of integers we move to the right. At this point, all the remaining elements have to be moved to the right once (that is, increased by $1$), and then listed in sorted order. 108 109 So, the answer is always several first elements of the suffix minima sequence, starting from the global minimum, and then all other elements, increased by $1$ and sorted in increased order. To find the point where we switch from the suffix minima sequence to the moved elements, it is convenient to precomute the minima, and keep a set of those elements we already move to the right. 110 111 This solution runs in $O(n \log n)$, along with many other. 112 113 **Code** 114 115 ``` 116 #include <bits/stdc++.h> 117 118 using namespace std; 119 120 #ifdef LOCAL 121 #define eprintf(...) fprintf(stderr, __VA_ARGS__) 122 #else 123 #define eprintf(...) 42 124 #endif 125 126 using ll = long long; 127 using ld = long double; 128 using D = double; 129 using uint = unsigned int; 130 template<typename T> 131 using pair2 = pair<T, T>; 132 133 #define pb push_back 134 #define mp make_pair 135 #define all(x) (x).begin(),(x).end() 136 #define fi first 137 #define se second 138 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 139 140 void solve() 141 { 142 int n; 143 scanf("%d", &n); 144 vector<int> a(n); 145 for (int i = 0; i < n; i++) scanf("%d", &a[i]); 146 vector<int> front(n); 147 int frontfront = n; 148 int frontback = n; 149 multiset<int> back; 150 for (int i = n - 1; i >= 0; i--) 151 { 152 if (frontfront >= frontback || a[i] <= front[frontfront]) front[--frontfront] = a[i]; 153 else back.insert(a[i] + 1); 154 while (frontfront < frontback && !back.empty() && front[frontback - 1] > *back.begin()) 155 { 156 back.insert(front[frontback - 1] + 1); 157 frontback--; 158 } 159 } 160 vector<int> answer; 161 for (int i = frontfront; i < frontback; i++) answer.pb(front[i]); 162 for (auto t : back) answer.pb(t); 163 for (auto t : answer) printf("%d ", t); 164 printf("\n"); 165 } 166 167 int main() 168 { 169 int NT = 1; 170 scanf("%d", &NT); 171 for (int T = 1; T <= NT; T++) 172 { 173 solve(); 174 } 175 return 0; 176 } 177 ``` 178 179 ### Div1C 180 181 First, we will use the idea of binary search on the answer. Let's assume we are currently checking if we can achieve the answer $k$. 182 183 We will iterate over all the necessary coordinates of the vertical lines. To do this, we note that it makes sense to iterate only over those where the lines coincide in the Y-coordinate with at least one of the points. It is obvious that in this case, the necessary vertical lines will be on the order of $O(n)$. 184 185 During the iteration over the vertical line, we will maintain two segment trees for the sum: one for the left half of the plane and the other for the right. $t_y$ in each of the segment trees will represent how many points have a Y-coordinate of $y$ in the corresponding half of the plane. In each of the segment trees, we will check if it is possible to divide the half-plane into two parts by a line parallel to the x-axis, so that there are at least $k$ points in both parts; and if this is possible, we will find the set of suitable lines — it will obviously be some segment $[y_{l}, \, y_{r}]$. If the intersection of the resulting segments in both segment trees is not empty, then we have found the answer. This can be done by descending the tree in $O(\log n)$ time. 186 187 Thus, the total time complexity of the described solution is $O(n \log^2 n)$. 188 189 **Code** 190 191 ``` 192 #include <math.h> 193 #include <unordered_set> 194 #include <unordered_map> 195 #include <map> 196 #include <iostream> 197 #include <fstream> 198 #include <vector> 199 #include <set> 200 #include <array> 201 #include <cstring> 202 #include <ctime> 203 #include <cassert> 204 #include <string_view> 205 #include <functional> 206 #include <sstream> 207 #include <numeric> 208 #include <cmath> 209 #include <deque> 210 #include <list> 211 #include <algorithm> 212 #include <iomanip> 213 214 using namespace std; 215 216 using i64 = long long; 217 using ui32 = unsigned int; 218 using ui64 = unsigned long long; 219 220 #define all(a) (a).begin(), (a).end() 221 222 223 struct Tree; 224 225 Tree* NewNode(); 226 227 struct Count { 228 int left = 0; 229 int right = 0; 230 void Add(int delta) { 231 left += delta; 232 if (delta < 0) { 233 right -= delta; 234 } 235 } 236 void operator += (const Count& c) { 237 left += c.left; 238 right += c.right; 239 } 240 241 int GetMin() { 242 return min(left, right); 243 } 244 }; 245 246 struct Tree { 247 Count count; 248 Tree* left = nullptr; 249 Tree* right = nullptr; 250 251 void Add(int l, int r, int p, int delta = 1) { 252 count.Add(delta); 253 if (r - l == 1) { 254 return; 255 } 256 int mid = (l + r) / 2; 257 if (p < mid) { 258 if (left == nullptr) { 259 left = NewNode(); 260 } 261 left->Add(l, mid, p, delta); 262 } else { 263 if (right == nullptr) { 264 right = NewNode(); 265 } 266 right->Add(mid, r, p, delta); 267 } 268 } 269 270 Count LeftCount() { 271 if (left) { 272 return left->count; 273 } 274 return {}; 275 } 276 Count RightCount() { 277 if (right) { 278 return right->count; 279 } 280 return {}; 281 } 282 283 void Remove(int l, int r, int p) { 284 Add(l, r, p, -1); 285 } 286 }; 287 288 Tree nodes[7000000]; 289 290 Tree* NewNode() { 291 static Tree* nextNode = nodes; 292 return nextNode++; 293 } 294 295 296 struct Solver { 297 struct Point { 298 int x, y; 299 bool operator < (const Point& p) const { 300 return x < p.x; 301 } 302 }; 303 304 int max = 0; 305 int bx = 0; 306 int by = 0; 307 308 bool FindBest(int l, int r, Tree* node, const Count& left = {}, const Count& right = {}) { 309 if (node == nullptr) { 310 return false; 311 } 312 int mid = (l + r) / 2; 313 Count newLeft = node->LeftCount(); 314 Count newRight = node->RightCount(); 315 newLeft += left; 316 newRight += right; 317 int mn = min(newLeft.GetMin(), newRight.GetMin()); 318 bool updated = false; 319 if (mn > max) { 320 max = mn; 321 by = mid; 322 updated = true; 323 } 324 if (mn == newLeft.GetMin()) { 325 if (FindBest(mid, r, node->right, newLeft, right)) { 326 return true; 327 } 328 } else { 329 if (FindBest(l, mid, node->left, left, newRight)) { 330 return true; 331 } 332 } 333 return updated; 334 } 335 336 void Solve(istream& cin, ostream& cout) { 337 int n; 338 cin >> n; 339 vector<Point> a(n); 340 int t9 = 1000000001; 341 #ifdef pperm 342 t9 = 100; 343 #endif 344 Tree* tree = NewNode(); 345 for (Point& p : a) { 346 cin >> p.x >> p.y; 347 tree->Add(-t9, t9, p.y); 348 } 349 sort(all(a)); 350 for (int i = 0; i < n;) { 351 int j = i + 1; 352 while (j < n && a[j].x == a[i].x) { 353 ++j; 354 } 355 if (FindBest(-t9, t9, tree)) { 356 bx = a[i].x; 357 } 358 for (;i < j; ++i) { 359 tree->Remove(-t9, t9, a[i].y); 360 361 } 362 } 363 cout << max << '\n' << bx << ' ' << by << endl; 364 } 365 }; 366 367 int main(int argc, char* args[]) { 368 #ifdef pperm 369 ifstream cin("/home/pperm86/My/Codeforces/input.txt"); 370 #endif 371 ios_base::sync_with_stdio(false); 372 cin.tie(NULL); 373 #ifndef pperm 374 srand(time(0)); 375 #endif 376 int T = 1; 377 cin >> T; 378 for (int iTest = 1; iTest <= T; ++iTest) { 379 Solver solver{}; 380 solver.Solve(cin, cout); 381 } 382 #ifdef pperm 383 cout << clock() / static_cast<double>(CLOCKS_PER_SEC) << endl; 384 #endif 385 return 0; 386 } 387 ``` 388 389 ### Div1D 390 391 We will compress the graph into strongly connected components. Inside a component, each runner can move between any pair of vertices and thus visit all. We will now solve the problem for a directed acyclic graph. 392 393 We will check for the existence of an answer. Suppose all runners already know the winning plan, and we will try to send them out so that each vertex is visited at least once. To do this, it is necessary to decompose the graph into paths such that: 394 395 * each vertex belongs to at least one path; 396 * no more than $a[i]$ paths start at each vertex (where $a[i]$ is the number of runners initially located at the vertex); 397 * paths may intersect. 398 399 Take the source $s$ and the sink $t$, and now a path can be represented as a sequence $s$, $u_1$, ..., $u_k$, $t$. 400 401 We will divide $u$ into $u_{in}$ and $u_{out}$ and will consider that a vertex $u$ belongs to least one transition from $u_{in}$ to $u_{out}$. We will draw the following edges: 402 403 * from $s$ to $u_{in}$ with capacity $cap = a[u]$; 404 * from $u_{in}$ to $u_{out}$ with $cap = inf$ and the condition of flow through the edge $f \geq 1$; 405 * from $u_{out}$ to $t$ with $cap = inf$; 406 * from $u_{out}$ to $v_{in}$ with $cap = inf$ for all edges (u, v) in the original graph. 407 408  This is equivalent to finding a flow with constraints in this graph. 409 410 To do this, we will create a dummy source $s'$ and sink $t'$, and now for each edge $(u_{in}, u_{out})$ with flow through it $1 \le f \le inf$, we will make the following replacements by drawing edges: 411 412 * from $u_{in}$ to $u_{out}$ with $cap = inf - 1$; 413 * from $s'$ to $u_{out}$ with $cap = 1$; 414 * from $u_{in}$ to $t'$ with $cap = 1$; 415 * from $t$ to $s$ with $cap = inf$. 416 417 Finding a flow that satisfies the constraints is equivalent to finding the maximum flow from $s'$ to $t'$, and if it equals the number of vertices, then the answer exists; otherwise, we can output $-1$ at this step. 418 419  420 421 Now we minimize the number of runners who initially know the plan. Note that: 422 423 * it makes no sense for runners to move until they know the plan; 424 * it makes no sense to pass the plan to more than one runner from one city. 425 426 We try to take this into account when constructing. Instead of adding edges from the source to $u_{in}$, we will do the following: 427 428 * create a vertex $u_{cnt}$ to control the number of runners and draw edges: 429 * from $s$ to $u_{cnt}$ with $cap = a[u]$; 430 * from $u_{cnt}$ to $u_{out}$ with $cap = a[u]$; 431 * from $u_{cnt}$ to $u_{in}$ with $cap = 1$, $cost = 1$. 432 * assign zero cost to all other edges. 433 434  This is equivalent to ensuring that all $a[i]$ runners learn the plan, but if no one comes to our city, we will personally tell exactly one runner from this number, paying $cost=1$ for that person. 435 436 The answer to the problem is the minimum cost of the maximum flow from $s'$ to $t'$ with this graph construction. The proof follows from the graph construction. 437 438 MCMF can be considered as $O(n^2m^2)$ or $O(n^3m)$ for any graphs, but it is worth noting that the flow value $f$ is limited to $n$, and we have a solution in $O(fnm)$ using Ford-Bellman or $O(fm\log n)$ using Dijkstra's algorithm with potentials. 439 440 Interestingly, we note that as a result, we obtained $3n$ vertices and $m + 7n$ edges. With careful implementation, MCMF fits well within TL. 441 442 **Code** 443 444 ``` 445 #define _CRT_SECURE_NO_WARNINGS 446 447 #include<iostream> 448 #include<fstream> 449 #include<vector> 450 #include<stack> 451 #include<queue> 452 #include<set> 453 #include<map> 454 #include<array> 455 #include<unordered_set> 456 #include<unordered_map> 457 #include<cstring> 458 #include<string> 459 #include<memory> 460 #include<iomanip> 461 #include<cassert> 462 #include<cmath> 463 #include<random> 464 #include<algorithm> 465 #include<chrono> 466 467 #pragma GCC optimize("O3,unroll-loops") 468 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 469 470 #define int long long 471 #define ld long double 472 #define endl '\n' 473 474 using namespace std; 475 476 constexpr int N = 500; 477 vector<int> g[N], gr[N], gcmp[N]; 478 int a[N], acmp[N], used[N], color[N], cur_color = 0; 479 vector<int> order, cmp; 480 481 void dfs1(int u) { 482 for (int v : g[u]) { 483 if (used[v] == 0) { 484 used[v] = 1; 485 dfs1(v); 486 } 487 } 488 order.push_back(u); 489 } 490 491 void dfs2(int u) { 492 for (int v : gr[u]) { 493 if (used[v] == 0) { 494 used[v] = 1; 495 dfs2(v); 496 } 497 } 498 color[u] = cur_color; 499 } 500 501 inline array<int, 3> getInd(int u) { 502 return { 3 * u, 3 * u + 1, 3 * u + 2 }; 503 } 504 505 constexpr int INF = 0x3f3f3f3f; 506 507 struct MCMF { 508 struct rib { 509 int b, u, c, f; 510 size_t back; 511 }; 512 513 MCMF(int size) : n(size), g_mcmf(size) {}; 514 515 int n; 516 vector<vector<rib>> g_mcmf; 517 518 void rebuild(int sz) { 519 n = sz, g_mcmf.clear(); g_mcmf.resize(sz); 520 } 521 522 void add_rib(int a, int b, int u, int c) { 523 rib r1 = { b, u, c, 0, g_mcmf[b].size() }; 524 rib r2 = { a, 0, -c, 0, g_mcmf[a].size() }; 525 g_mcmf[a].push_back(r1); 526 g_mcmf[b].push_back(r2); 527 } 528 529 pair<int, int> get_flow(int s, int t, int maxflow = INF) { 530 int flow = 0, cost = 0; 531 while (flow < maxflow) { 532 vector<int> id(n, 0); 533 vector<int> d(n, INF); 534 vector<int> q(n); 535 vector<int> p(n); 536 vector<size_t> p_rib(n); 537 int qh = 0, qt = 0; 538 q[qt++] = s; 539 d[s] = 0; 540 while (qh != qt) { 541 int v = q[qh++]; 542 id[v] = 2; 543 if (qh == n) qh = 0; 544 for (size_t i = 0; i < g_mcmf[v].size(); ++i) { 545 rib& r = g_mcmf[v][i]; 546 if (r.f < r.u && d[v] + r.c < d[r.b]) { 547 d[r.b] = d[v] + r.c; 548 if (id[r.b] == 0) { 549 q[qt++] = r.b; 550 if (qt == n) qt = 0; 551 } 552 else if (id[r.b] == 2) { 553 if (--qh == -1) qh = n - 1; 554 q[qh] = r.b; 555 } 556 id[r.b] = 1; 557 p[r.b] = v; 558 p_rib[r.b] = i; 559 } 560 } 561 } 562 563 if (d[t] == INF) break; 564 int addflow = maxflow - flow; 565 for (int v = t; v != s; v = p[v]) { 566 int pv = p[v]; size_t pr = p_rib[v]; 567 addflow = min(addflow, g_mcmf[pv][pr].u - g_mcmf[pv][pr].f); 568 } 569 for (int v = t; v != s; v = p[v]) { 570 int pv = p[v]; size_t pr = p_rib[v], r = g_mcmf[pv][pr].back; 571 g_mcmf[pv][pr].f += addflow; 572 g_mcmf[v][r].f -= addflow; 573 cost += g_mcmf[pv][pr].c * addflow; 574 } 575 flow += addflow; 576 } 577 return { flow, cost }; 578 } 579 }; 580 581 void solve() { 582 583 for (int i =0 ; i < N; i++) 584 { 585 g[i] = {}; 586 gr[i] = {}; 587 gcmp[i] = {}; 588 } 589 memset(a, 0, sizeof a); 590 memset(acmp, 0, sizeof acmp); 591 memset(used, 0, sizeof used); 592 memset(color, 0, sizeof color); 593 cur_color = 0; 594 order = {}; 595 cmp = {}; 596 597 int n, m; cin >> n >> m; 598 for (int i = 0; i < n; i++) { 599 g[i].clear(); 600 gr[i].clear(); 601 } 602 603 for (int i = 0; i < n; i++) cin >> a[i]; 604 605 for (int i = 0; i < m; i++) { 606 int u, v; cin >> u >> v; u--, v--; 607 g[u].push_back(v); 608 gr[v].push_back(u); 609 } 610 611 order.clear(); 612 memset(used, 0, sizeof(used[0]) * n); 613 for (int i = 0; i < n; i++) { 614 if (used[i] == 0) { 615 used[i] = 1; 616 dfs1(i); 617 } 618 } 619 620 memset(used, 0, sizeof(used[0]) * n); 621 for (int i = 0; i < n; i++) { 622 int u = order[n - i - 1]; 623 if (used[u] == 0) { 624 used[u] = 1; 625 dfs2(u); 626 cur_color++; 627 } 628 } 629 630 // for (int i = 0; i < n; i++) cout << color[i] << " "; cout << endl; 631 632 memset(acmp, 0, sizeof(acmp[0]) * cur_color); 633 for (int i = 0; i < n; i++) { 634 acmp[color[i]] += a[i]; 635 for (int v : g[i]) { 636 if (color[i] != color[v]) { 637 gcmp[color[i]].push_back(color[v]); 638 } 639 } 640 } 641 642 for (int i = 0; i < cur_color; i++) { 643 auto& e = gcmp[i]; 644 sort(e.begin(), e.end()); 645 e.erase(unique(e.begin(), e.end()), e.end()); 646 647 // cout << i << " " << acmp[i] << ": "; 648 // for (int v : e) cout << v << " "; cout << endl; 649 } 650 651 int s = 3 * cur_color, t = s + 1, so = t + 1, to = so + 1; 652 MCMF gg(to + 1); 653 654 for (int i = 0; i < cur_color; i++) { 655 auto [uin, uout, ucnt] = getInd(i); 656 gg.add_rib(s, ucnt, acmp[i], 0); 657 gg.add_rib(ucnt, uin, 1, 1); 658 gg.add_rib(ucnt, uout, INF, 0); 659 660 gg.add_rib(uin, uout, INF, 0); 661 gg.add_rib(uout, t, INF, 0); 662 663 gg.add_rib(so, uout, 1, 0); 664 gg.add_rib(uin, to, 1, 0); 665 } 666 667 gg.add_rib(t, s, INF, 0); 668 669 for (int i = 0; i < cur_color; i++) { 670 auto [uin, uout, ucnt] = getInd(i); 671 for (int v : gcmp[i]) { 672 auto [vin, vout, vcnt] = getInd(v); 673 gg.add_rib(uout, vin, INF, 0); 674 } 675 } 676 677 auto [flow, cost] = gg.get_flow(so, to); 678 // cout << flow << " " << cost << endl; 679 680 if (flow < cur_color) { 681 cout << -1 << endl; 682 return; 683 } 684 685 cout << cost << endl; 686 } 687 688 signed main() { 689 // freopen("input.txt", "r", stdin); 690 ios_base::sync_with_stdio(false); 691 cin.tie(0); cout.tie(0); 692 693 int q; cin >> q; while (q--) 694 solve(); 695 } 696 ``` 697 698 ### Div1E1+E2 699 700 For convenience, we will call groups that include certain cities. 701 702 The key condition is that each specialization can correspond to no more than one task. Thus, cities from different groups must have "practically sorted" strength values as the group order increases. 703 704 Let $[l_i, r_i]$ denote the segment that includes all the strengths of the cities in group $i$, where $r_i$ is the maximum strength of a city from this group, and $l_i$ is the minimum. If $l_i \le r_{i+2}$, it is impossible to build a contest, as there must be at least a difference of 2 tasks between the cities corresponding to $l_i$ and $r_{i+2}$, but they can differ by at most 1 task in specialization. After this, the problem reduces to considering two neighboring groups and subsequently checking the task difficulties for compliance with the linear conditions of each group. 705 706 Let's consider two cases: 707 708 * If $l_i \ge r_{i+1}$, it is sufficient to add a few tasks (specifically, just 2) of difficulty from the segment $[r_{i+1} + 1, l_i]$ to maintain order. 709 * Otherwise, each city in the $i$-th group that lies in the intersection must solve a task with its specialization. In this case, no task can be in the segment $[l_i + 1, r_{i+1}]$, as the city with the highest strength in group $i+1$ will solve at least as many tasks as the weakest city in group $i$, which we cannot allow. To maintain order with the other groups, it is sufficient to add 2 tasks of difficulty $r_{i+1} + 1$ (unlike the first case, due to the fact that $l_i \le r_{i+2}$ cannot occur, we can immediately determine the appropriate task difficulty, but they can be arranged using the same algorithm as for the first case). 710 711 It can be noted that when adding pairs of tasks, they need to choose an unused specification (since we are not using it in principle, but otherwise it may cause collisions). 712 713 We conclude that we need to arrange tasks with a specified specification that a city from the intersection of groups can solve, meaning its difficulty must not exceed the wisdom of that city, and also arrange 2 tasks of certain difficulties to maintain order between groups. These difficulties arise from possible intersections with other groups when using $r_{i+1} + 1$ as the task difficulty and possible specification collisions of cities, which may allow a city from a weaker group to solve a task that we did not intend for it, thus violating the strictness conditions between groups. 714 715 Most problems cannot arise when $m=2$, so what has been said above is already a solution (without minor adjustments) to the simple version of the problem. 716 717 First, we will solve how to choose the difficulty for tasks with a specific specification. To do this, we will prohibit using the task specification corresponding to cities that form the second case (i.e., from the $i+1$-th group) with difficulty $[l_i, b_j]$, where j is the number of such a city. Also, as mentioned, we cannot have a task from the segment $[l_i + 1, r_{i+1}]$ regardless of the type. To determine the difficulty, it is sufficient to set it to the maximum possible (equal to wisdom) and then gradually decrease it until we reach an allowed difficulty. 718 719 To resolve the problem from the first case, we will place barriers with 2 tasks of difficulty equal to the strength of a certain city wherever possible. 720 721 If there exists an answer for the given configuration, we will guarantee to construct it this way, using no more than $3 \cdot n$ tasks. After all calculations, we need to check whether the contest we constructed meets the problem's conditions and output -1 otherwise. 722 723 **Code** 724 725 ``` 726 /** 727 * author: tourist 728 * created: 01.12.2024 18:36:51 729 **/ 730 #undef _GLIBCXX_DEBUG 731 732 #include <bits/stdc++.h> 733 734 using namespace std; 735 736 #ifdef LOCAL 737 #include "algo/debug.h" 738 #else 739 #define debug(...) 42 740 #endif 741 742 int main() { 743 ios::sync_with_stdio(false); 744 cin.tie(nullptr); 745 int tt; 746 cin >> tt; 747 while (tt--) { 748 int n, m; 749 cin >> n >> m; 750 vector<int> a(n), b(n), c(n); 751 set<int> s; 752 for (int i = 0; i < n; i++) { 753 cin >> a[i] >> b[i] >> c[i]; 754 s.insert(c[i]); 755 } 756 vector<vector<int>> vs(m); 757 for (int i = 0; i < m; i++) { 758 int foo; 759 cin >> foo; 760 vs[i].resize(foo); 761 for (int j = 0; j < foo; j++) { 762 cin >> vs[i][j]; 763 --vs[i][j]; 764 } 765 } 766 const int inf = int(1.01e9); 767 vector<int> min_a(m, inf); 768 vector<int> max_a(m, -1); 769 for (int i = 0; i < m; i++) { 770 for (int j : vs[i]) { 771 min_a[i] = min(min_a[i], a[j]); 772 max_a[i] = max(max_a[i], a[j]); 773 } 774 } 775 auto Unify = [&](vector<pair<int, int>>& bad) { 776 sort(bad.begin(), bad.end()); 777 int ptr = 0; 778 for (int i = 1; i < int(bad.size()); i++) { 779 if (bad[i].first <= bad[ptr].second + 1) { 780 bad[ptr].second = max(bad[ptr].second, bad[i].second); 781 } else { 782 bad[++ptr] = bad[i]; 783 } 784 } 785 bad.resize(ptr + 1); 786 }; 787 vector<pair<int, int>> bad; 788 for (int id = 0; id < m - 1; id++) { 789 if (min_a[id] < max_a[id + 1]) { 790 bad.emplace_back(min_a[id] + 1, max_a[id + 1]); 791 } 792 } 793 Unify(bad); 794 vector<int> ctr(n); 795 for (int i = 0; i < m; i++) { 796 for (int x : vs[i]) { 797 ctr[x] = i; 798 } 799 } 800 vector<pair<int, int>> tasks; 801 int unused = 0; 802 vector<int> order(n); 803 iota(order.begin(), order.end(), 0); 804 sort(order.begin(), order.end(), [&](int i, int j) { 805 return a[i] > a[j]; 806 }); 807 multiset<int> before, after; 808 for (int i = 0; i < n; i++) { 809 after.insert(ctr[i]); 810 } 811 { 812 int beg = 0; 813 while (beg < n) { 814 int end = beg; 815 while (end + 1 < n && a[order[end + 1]] == a[order[end]]) { 816 end += 1; 817 } 818 for (int i = beg; i <= end; i++) { 819 before.insert(ctr[order[i]]); 820 after.erase(after.find(ctr[order[i]])); 821 } 822 if (!before.empty() && !after.empty() && *prev(before.end()) <= *after.begin()) { 823 for (int i = 0; i < 2; i++) { 824 do { 825 unused += 1; 826 } while (s.find(unused) != s.end()); 827 tasks.emplace_back(a[order[end]], unused); 828 } 829 } 830 beg = end + 1; 831 } 832 } 833 map<int, int> add; 834 for (int id = 0; id < m - 1; id++) { 835 for (int i : vs[id]) { 836 if (a[i] <= max_a[id + 1]) { 837 if (add.find(c[i]) == add.end()) { 838 add[c[i]] = b[i]; 839 } else { 840 add[c[i]] = min(add[c[i]], b[i]); 841 } 842 } 843 } 844 } 845 map<int, vector<pair<int, int>>> kill; 846 for (int id = 1; id < m; id++) { 847 for (int i : vs[id]) { 848 if (a[i] >= min_a[id - 1]) { 849 kill[c[i]].push_back({min_a[id - 1] + 1, b[i]}); 850 } 851 } 852 } 853 for (auto& [type, x] : add) { 854 auto& k = kill[type]; 855 Unify(k); 856 int dif = x; 857 while (true) { 858 bool changed = false; 859 { 860 auto it = lower_bound(bad.begin(), bad.end(), make_pair(dif + 1, -1)); 861 if (it != bad.begin()) { 862 it = prev(it); 863 if (it->second >= dif) { 864 dif = it->first - 1; 865 changed = true; 866 } 867 } 868 } 869 { 870 auto it = lower_bound(k.begin(), k.end(), make_pair(dif + 1, -1)); 871 if (it != k.begin()) { 872 it = prev(it); 873 if (it->second >= dif) { 874 dif = it->first - 1; 875 changed = true; 876 } 877 } 878 } 879 if (!changed) { 880 break; 881 } 882 } 883 tasks.emplace_back(dif, type); 884 } 885 debug(tasks); 886 vector<int> all; 887 map<int, int> spec; 888 for (auto& [x, y] : tasks) { 889 all.push_back(x); 890 assert(spec.find(y) == spec.end()); 891 spec[y] = x; 892 } 893 sort(all.begin(), all.end()); 894 vector<int> solved(n); 895 for (int i = 0; i < n; i++) { 896 solved[i] = int(upper_bound(all.begin(), all.end(), a[i]) - all.begin()); 897 if (spec.find(c[i]) != spec.end() && spec[c[i]] > a[i] && spec[c[i]] <= b[i]) { 898 solved[i] += 1; 899 } 900 } 901 vector<int> min_solved(m, inf); 902 vector<int> max_solved(m, -1); 903 for (int i = 0; i < m; i++) { 904 for (int j : vs[i]) { 905 min_solved[i] = min(min_solved[i], solved[j]); 906 max_solved[i] = max(max_solved[i], solved[j]); 907 } 908 } 909 bool win = true; 910 for (int id = 0; id < m - 1; id++) { 911 if (min_solved[id] <= max_solved[id + 1]) { 912 win = false; 913 break; 914 } 915 } 916 if (win) { 917 cout << tasks.size() << '\n'; 918 for (auto& [x, y] : tasks) { 919 cout << x << " " << y << '\n'; 920 } 921 } else { 922 cout << -1 << '\n'; 923 } 924 } 925 return 0; 926 } 927 ``` 928 929 ### Div1F1 930 931 It can be noted that if the string contains the correct number of symbols 'Y', 'D', 'X' and does not have two consecutive identical symbols, then it can be obtained using the given operations. 932 933 To demonstrate this, we will provide an algorithm that constructs a sequence of operations leading to the desired string. We will start from the end (from the string we want to obtain to the empty string) gradually removing symbols. 934 935 Let's look at the current string. Without loss of generality, let its first symbol be 'Y'. Then the string must contain the substring 'DX' and/or the substring 'XD'. This is true because for the absence of 'DX' and 'XD', it is necessary that between any pair of symbols not equal to 'Y', there is at least one symbol 'Y'. This can be achieved at best by placing 'Y' between every symbol. Thus, the number of symbols not equal to 'Y' with $n-1$ 'Y' can be at most $n$. But $3n-1 \gt n$ when $n \gt 0$. 936 937 Thus, the string has the form 'Y...ADXB...'. 938 939 If A $\neq$ B, we can remove the symbols 'Y', 'D', 'X' and nothing will break. 940 941 If A = B, then A = B = 'Y', since A != 'D' and A != 'X'. 942 943 Then the string has the form 'Y...YDXY...', and we can remove the substring 'YDX' and still have an unbroken string 'Y...Y...'. 944 945 ### Div1F2 946 947 We will isolate substrings from the string that consist entirely of '?'. For each, we will denote its length as $len_i$ and the two neighboring symbols (standing to the left and right) as $l_i$, $r_i$. (If the right and/or left symbol is absent, we will take it as '#', a symbol that does not match any of our interests). 948 949 We will write trivial constraints on the number of available symbols of each type on the segment. It is obvious that the number of symbols of each type cannot exceed $\frac{len_i+1}{2}$: we will place one symbol for every other symbol. But if, for example, we had a symbol 'Y' on the left, the number of positions where we can place 'Y' decreases by $1$. In total, we can place no more than $\frac{len+1-(l_i=b)-(r_i=b)}{2}$ symbols of type b. We will write such constraints for each type of symbol and denote them as $Y, D, X$ respectively. 950 951 It turns out that we can arrange $y$ symbols 'Y', $d$ symbols 'D' and $x$ symbols 'X' if and only if $y+d+x=len_i$ and $0\leq y \leq Y, 0 \leq d \leq D, 0 \leq x \leq X$. This can be proven by induction or checked with stress tests on small values. From this, we conclude that in order to be able to arrange $x, d, y$ symbols of each type, the inequalities above must hold. 952 953 From the equality $y+d+x=len_i$, we express $d=len_i - (x+y)$. 954 955 This results in three constraints: $0\leq x \leq X, 0 \leq y \leq Y, 0 \leq len_i - (x+y) \leq D$. The first two form a rectangle, and the third cuts off two corners at a $45$ degree angle. This is a convex polygon. 956 957 Thus, if for each segment of '?' we write a polygon and sum them using Minkowski sum, we will obtain constraints for the entire string. 958 959 Since in the Minkowski sum (after merging collinear consecutive segments) there will be at most 6 points, we can write a greedy algorithm that sequentially tries to match the required symbol to each '?'. 960 961 The final asymptotic complexity is $O(n)$ with some constant. 962 963 **Code** 964 965 ``` 966 #pragma GCC optimize("Ofast") 967 #include <iostream> 968 #include <cmath> 969 #include <cstdint> 970 #include <vector> 971 #include <string> 972 #include <iomanip> 973 #include <set> 974 #include <map> 975 #include <unordered_map> 976 #include <unordered_set> 977 #include <algorithm> 978 #include <functional> 979 #include <queue> 980 #include <fstream> 981 #include <random> 982 //#include <numbers> 983 #include <optional> 984 #include <deque> 985 #include <sstream> 986 #include <list> 987 #include <chrono> 988 #include <thread> 989 #include <cassert> 990 991 using namespace std; 992 using i64 = int64_t; 993 using ui64 = uint64_t; 994 #define YN(b) if (b) cout << "YES\n"; else cout << "NO\n"; 995 996 template<typename T> 997 istream& operator>>(istream& is, vector<T>& v) { for (auto &e: v) { is >> e; } return is; } 998 999 template<typename T> 1000 ostream& operator<<(ostream& os, vector<T>& v) { for (auto &e: v) { os << e << " "; } return os; } 1001 1002 template<typename T, typename V> 1003 istream& operator>>(istream& is, pair<T, V>& v) { return is >> v.first >> v.second; } 1004 1005 template<typename T, typename V> 1006 ostream& operator<<(ostream& os, pair<T, V>& v) { return os << v.first << " " << v.second; } 1007 1008 const int64_t md = 1e9+7; 1009 1010 int dx[4] = {-1, 0, 1, 0}; 1011 1012 inline int64_t sqr(int64_t x) { 1013 return x * x; 1014 } 1015 1016 inline int popcount(int64_t x) { 1017 int c = 0; 1018 while (x) c += x & 1, x >>= 1; 1019 return c; 1020 } 1021 1022 pair<int64_t, int64_t> inter(pair<int64_t, int64_t> a, pair<int64_t, int64_t> b) { 1023 return {max(a.first, b.first), min(a.second, b.second)}; 1024 } 1025 1026 struct pt { 1027 using T = int; 1028 using V = int64_t; 1029 T x = 0, y = 0; 1030 pt() = default; 1031 pt(T x, T y) : x(x), y(y) {} 1032 inline pt& operator-=(const pt& other) { 1033 x -= other.x; 1034 y -= other.y; 1035 return *this; 1036 } 1037 inline pt operator-(const pt& other) const { 1038 pt copy(*this); 1039 copy -= other; 1040 return copy; 1041 } 1042 inline pt& operator+=(const pt& other) { 1043 x += other.x; 1044 y += other.y; 1045 return *this; 1046 } 1047 inline pt operator+(const pt& other) const { 1048 pt copy(*this); 1049 copy += other; 1050 return copy; 1051 } 1052 V operator^(const pt& other) const { 1053 return (V)x * other.y - (V)y * other.x; 1054 } 1055 V operator*(const pt& other) const { 1056 return (V)x * other.x + (V)y * other.y; 1057 } 1058 void print() const { 1059 cerr << x << " " << y << "\n"; 1060 } 1061 bool operator==(const pt&) const = default; 1062 }; 1063 1064 inline bool in_triangle(const pt& a, const pt& b, const pt& c, const pt& point) { 1065 int64_t s1 = abs((b - a) ^ (c - a)); 1066 int64_t s2 = abs((a - point) ^ (b - point)) + abs((b - point) ^ (c - point)) + abs((c - point) ^ (a - point)); 1067 return s1 == s2; 1068 } 1069 1070 struct mi { 1071 size_t i = 0; 1072 size_t ni = 1; 1073 const size_t m; 1074 mi(size_t m) : m(m) {} 1075 void add() { 1076 ++i; 1077 if (++ni == m) ni = 0; 1078 } 1079 }; 1080 int64_t orientation(pt a, pt b, pt c) { 1081 return -((int64_t)a.x * (b.y - c.y) + (int64_t)b.x * (c.y - a.y) + (int64_t)c.x * (a.y - b.y)); 1082 } 1083 inline bool comp(pt a, pt b) { 1084 auto cp = a ^ b; 1085 if (!cp) { 1086 return a * a < b * b; 1087 } 1088 return (pt::V)a.x * b.x < 0 ? (a.x > b.x) : cp > 0; 1089 } 1090 1091 struct NMP { 1092 array<pt, 13> pts; 1093 int len = 0; 1094 template<typename... Args> 1095 void emplace_back(Args&& ...p) { 1096 new (&pts[len++]) pt(p...); 1097 } 1098 void push_back(const pt& x) { 1099 pts[len++] = x; 1100 } 1101 pt& operator[](size_t x) { 1102 return pts[x]; 1103 } 1104 size_t size() const { 1105 return len; 1106 } 1107 1108 const pt& operator[](size_t x) const { 1109 return pts[x]; 1110 } 1111 pt* begin() { 1112 return &pts[0]; 1113 } 1114 pt* end() { 1115 return &pts[len]; 1116 } 1117 void resize(size_t x) { 1118 len = x; 1119 } 1120 }; 1121 1122 struct poly { 1123 using P = pt; 1124 NMP pts; 1125 void add(const P& p) { 1126 pts.push_back(p); 1127 } 1128 1129 template<typename... Args> 1130 void emplace(Args&& ...p) { 1131 pts.emplace_back(p...); 1132 } 1133 1134 void sort() { 1135 size_t min_id = 0; 1136 for (size_t i = 1; i < pts.size(); ++i) { 1137 if (pts[i].y < pts[min_id].y || (pts[i].y == pts[min_id].y && pts[i].x < pts[min_id].x)) { 1138 min_id = i; 1139 } 1140 } 1141 std::rotate(pts.begin(), pts.begin() + min_id, pts.end()); 1142 auto p0 = pts[0]; 1143 std::sort(pts.begin(), pts.end(), [&](const P& a, const P& b) { 1144 auto o = orientation(p0, a, b); 1145 if (!o) 1146 return (int64_t)(p0.x-a.x)*(p0.x-a.x) + (int64_t)(p0.y-a.y)*(p0.y-a.y) 1147 < (int64_t)(p0.x-b.x)*(p0.x-b.x) + (int64_t)(p0.y-b.y)*(p0.y-b.y); 1148 return o < 0; 1149 }); 1150 } 1151 1152 void no_coll() { 1153 if (pts.size() < 3) { 1154 return; 1155 } 1156 size_t ptr = 1; 1157 for (size_t j = 2; j < pts.size(); ++j) { 1158 if ((pts[ptr] - pts[ptr - 1]) ^ (pts[j] - pts[ptr])) { 1159 pts[++ptr] = pts[j]; 1160 continue; 1161 } 1162 pts[ptr] = pts[j]; 1163 } 1164 pts.resize(ptr + 1); 1165 } 1166 1167 poly operator+(const poly& other) const { 1168 if (pts.size() == 1) { 1169 poly c(other); 1170 for (auto& p: c.pts) p += pts[0]; 1171 return c; 1172 } 1173 if (other.pts.size() < pts.size()) { 1174 return other + *this; 1175 } 1176 // size at least 2s 1177 poly res; 1178 mi i(pts.size()), j(other.pts.size()); 1179 1180 while (i.i < pts.size() && j.i < other.pts.size()) { 1181 res.emplace(pts[i.i] + other.pts[j.i]); 1182 auto a = (pts[i.ni] - pts[i.i]); 1183 auto b = (other.pts[j.ni] - other.pts[j.i]); 1184 auto cp = a ^ b; 1185 if (cp < 0) { 1186 j.add(); 1187 } else if (cp > 0) { 1188 i.add(); 1189 } else if ((P::V)a.y * b.y >= 0) { 1190 i.add(); 1191 j.add(); 1192 } else if (a.y > b.y) { 1193 i.add(); 1194 } else { 1195 j.add(); 1196 } 1197 } 1198 while (i.i < pts.size()) { 1199 res.emplace(pts[i.i] + other.pts[0]); 1200 i.add(); 1201 } 1202 1203 while (j.i < other.pts.size()) { 1204 res.emplace(pts[0] + other.pts[j.i]); 1205 j.add(); 1206 } 1207 1208 res.no_coll(); 1209 return res; 1210 } 1211 1212 void print() { 1213 for (auto &e: pts) { 1214 cout << "(" << e.x << " " << e.y << ") "; 1215 } 1216 cout << "\n"; 1217 } 1218 1219 bool in(const pt& p) const { 1220 if (pts.size() == 1) { 1221 return pts[0] == p; 1222 } 1223 if (pts.size() == 2) { 1224 return ((pts[0] - p) ^ (pts[1] - p)) == 0 1225 && min(pts[0].x, pts[1].x) <= p.x && p.x <= max(pts[0].x, pts[1].x) 1226 && min(pts[0].y, pts[1].y) <= p.y && p.y <= max(pts[0].y, pts[1].y); 1227 } 1228 for (int i = 2; i < pts.size(); ++i) { 1229 if (in_triangle(pts[i], pts[i - 1], pts[0], p)) { 1230 return true; 1231 } 1232 } 1233 return false; 1234 } 1235 }; 1236 1237 struct co { 1238 array<int, 3> cst {}; 1239 poly p; 1240 co() { 1241 p.emplace(0, 0); 1242 } 1243 1244 co(int l, int a, int b) { 1245 cst = { 1246 max(0, 1 + l - (a == 0) - (b == 0)) / 2, 1247 max(0, 1 + l - (a == 1) - (b == 1)) / 2, 1248 max(0, 1 + l - (a == 2) - (b == 2)) / 2 1249 }; 1250 p.emplace(min(cst[0], l - cst[2]), max(0, l - cst[0] - cst[2])); 1251 p.emplace(min(cst[0], l), max(0, l - cst[0] - cst[2])); 1252 p.emplace(cst[0], min(cst[1], l - cst[0])); 1253 p.emplace(min(l - cst[1], cst[0]), cst[1]); 1254 p.emplace(max(0, l - cst[1] - cst[2]), min(l, cst[1])); 1255 p.emplace(max(0, l - cst[1] - cst[2]), min(cst[1], l - cst[2])); 1256 p.sort(); 1257 p.no_coll(); 1258 } 1259 1260 co operator+(const co& rhs) { 1261 co res; 1262 res.p = p + rhs.p; 1263 for (int j = 0; j < 3; ++j) res.cst[j] = cst[j] + rhs.cst[j]; 1264 return res; 1265 } 1266 1267 bool ok(int x, int y, int z) { 1268 return x <= cst[0] && y <= cst[1] && z <= cst[2]; 1269 } 1270 1271 bool in(int x, int y, int z) { 1272 return ok(x, y, z) && p.in(pt(x, y)); 1273 } 1274 }; 1275 1276 char idx[128]{}; 1277 string ydx = "YDX"; 1278 1279 struct fenwick { 1280 fenwick(int x) : t(x), n(x) {} 1281 vector<int> t; 1282 int n; 1283 int sum (int r) { 1284 int result = 0; 1285 for (; r >= 0; r = (r & (r+1)) - 1) 1286 result += t[r]; 1287 return result; 1288 } 1289 1290 void inc (int i, int delta) { 1291 for (; i < n; i = (i | (i+1))) 1292 t[i] += delta; 1293 } 1294 }; 1295 1296 using S = std::list<pair<short, int>>; 1297 1298 struct cmp { 1299 bool operator()(S::iterator a, S::iterator b) const { 1300 return a->second < b->second; 1301 }; 1302 }; 1303 1304 auto encode1(auto a, auto b) { 1305 return a * 256 + b; 1306 }; 1307 1308 auto encode(auto it) { 1309 auto prev = it++; 1310 return encode1(prev->first, it->first); 1311 }; 1312 1313 auto erase_char(auto& curr_pos, S& str, fenwick& alive, auto& pos, auto it) { 1314 auto curr = it; 1315 auto prev = --it; 1316 it = curr; 1317 auto next = ++it; 1318 if (next != str.end()) { 1319 if (!pos[encode(curr)].count(curr)) { 1320 exit(-1); 1321 } 1322 pos[encode(curr)].erase(curr); 1323 } 1324 if (prev != str.end()) { 1325 if (!pos[encode(prev)].count(prev)) { 1326 exit(-1); 1327 } 1328 pos[encode(prev)].erase(prev); 1329 } 1330 curr_pos.emplace_back(curr->first, alive.sum(curr->second) - 1); 1331 alive.inc(curr->second, -1); 1332 str.erase(curr); 1333 if (next != str.end() && prev != str.end()) { 1334 auto p = prev; 1335 ++p; 1336 if (p != next) { 1337 exit(-1); 1338 } 1339 pos[encode(prev)].emplace(prev); 1340 } 1341 }; 1342 1343 bool is_ok(S::iterator x, S::iterator end) { 1344 auto curr = x; 1345 auto prev = --x; 1346 auto next = ++curr; 1347 if (prev != end && next != end) { 1348 return prev->first != next->first; 1349 } 1350 return true; 1351 } 1352 1353 auto got(auto& curr_pos, auto& str, auto& alive, auto& pos, vector<S::iterator> t) { 1354 for (auto &e: t) { 1355 erase_char(curr_pos, str, alive, pos, e); 1356 } 1357 }; 1358 1359 auto relax(auto& curr_pos, auto& str, auto& alive, auto& pos, short sym, short co) { 1360 auto &v = pos[co]; 1361 auto it = *v.begin(); 1362 auto A = it; 1363 auto prev = --it; 1364 it = A; 1365 auto B = ++it; 1366 auto next = ++it; 1367 if (prev != str.end() && next != str.end() && prev->first == next->first) { 1368 if (prev->first != sym) { 1369 exit(-1); 1370 } 1371 got(curr_pos, str, alive, pos, {prev, A, B}); 1372 return false; 1373 } 1374 1375 got(curr_pos, str, alive, pos, {A, B}); 1376 return true; 1377 }; 1378 1379 vector<array<pair<char, int>, 3>> solve_str(const string& s) { 1380 S str; 1381 fenwick alive(s.size()); 1382 1383 for (int i = 0; i < s.size(); ++i) { 1384 str.emplace_back(s[i], i); 1385 alive.inc(i, 1); 1386 } 1387 1388 auto it = str.begin(); 1389 1390 map<int, set<decltype(it), cmp>> pos; 1391 while (it != str.end()) { 1392 auto prev = it++; 1393 if (it == str.end()) break; 1394 pos[encode(prev)].emplace(prev); 1395 } 1396 vector<pair<char, int>> curr_pos; 1397 vector<decltype(it)> curr_t; 1398 vector<array<pair<char, int>, 3>> res; 1399 while (str.size()) { 1400 it = str.begin(); 1401 auto curr = it++; 1402 if (it == str.end()) { 1403 exit(-1); 1404 } 1405 short code = curr->first; 1406 erase_char(curr_pos, str, alive, pos, curr); 1407 1408 array<int, 2> candidates; 1409 if (code == 'Y') { 1410 candidates[0] = encode1('D', 'X'); 1411 candidates[1] = encode1('X', 'D'); 1412 } else if (code == 'X') { 1413 candidates[0] = encode1('D', 'Y'); 1414 candidates[1] = encode1('Y', 'D'); 1415 } else { 1416 candidates[0] = encode1('Y', 'X'); 1417 candidates[1] = encode1('X', 'Y'); 1418 } 1419 bool ok = 0; 1420 while (!ok) { 1421 for (auto &c: candidates) { 1422 if (!pos[c].size()) { 1423 continue; 1424 } 1425 if (relax(curr_pos, str, alive, pos, code, c)) { 1426 ok = 1; 1427 res.emplace_back(); 1428 res.back()[0] = curr_pos[2]; 1429 res.back()[1] = curr_pos[1]; 1430 res.back()[2] = curr_pos[0]; 1431 curr_pos.clear(); 1432 break; 1433 } 1434 // A...ABCA, ABC removed 1435 res.emplace_back(); 1436 for (int j = 0; j < 3; ++j) { 1437 res.back()[j] = curr_pos.back(); // removed 1438 res.back()[j].second += 1; 1439 curr_pos.pop_back(); 1440 } 1441 break; 1442 } 1443 } 1444 } 1445 reverse(res.begin(), res.end()); 1446 return res; 1447 } 1448 1449 bool check(const string& s) { 1450 array<int, 3> cnt{}; 1451 char prev = -1; 1452 for (auto &e: s) { 1453 if (e == '?') { 1454 return false; 1455 } 1456 if (e != 'Y' && e != 'D' && e != 'X') { 1457 return false; 1458 } 1459 if (e == prev) return false; 1460 prev = e; 1461 ++cnt[idx[e]]; 1462 } 1463 return cnt[0] == s.size() / 3 && cnt[1] == s.size() / 3 && cnt[2] == s.size() / 3; 1464 } 1465 1466 optional<string> solve_fast1(string v) { 1467 auto sv = v; 1468 int N = v.size() / 3; 1469 array<int, 3> rem{N, N, N}; 1470 for (auto &e: v) { 1471 if (e == '?') continue; 1472 --rem[idx[e]]; 1473 } 1474 if (rem[0] < 0 || rem[1] < 0 || rem[2] < 0) return {}; 1475 vector<co> mink; 1476 vector<pair<int, int>> segs; 1477 for (int i = 0; i < v.size(); ++i) { 1478 if (v[i] != '?') continue; 1479 int j = i + 1; 1480 while (j < v.size() && v[j] == '?') ++j; 1481 mink.emplace_back(j - i, i > 0 ? idx[v[i - 1]] : 3, j < v.size() ? idx[v[j]] : 3); 1482 segs.emplace_back(i, j - 1); 1483 i = j - 1; 1484 } 1485 reverse(mink.begin(), mink.end()); 1486 reverse(segs.begin(), segs.end()); 1487 for (int i = 1; i < mink.size(); ++i) { 1488 mink[i] = mink[i - 1] + mink[i]; 1489 } 1490 if (mink.size()) { 1491 mink.pop_back(); 1492 } 1493 while (segs.size()) { 1494 auto seg = segs.back(); 1495 segs.pop_back(); 1496 auto mk = mink.size() ? mink.back() : co(); 1497 if (mink.size()) { 1498 mink.pop_back(); 1499 } 1500 char prev = idx[seg.first ? v[seg.first - 1] : '?']; 1501 char next_r = idx[seg.second + 1 < v.size() ? v[seg.second + 1] : '?']; 1502 while (seg.first <= seg.second) { 1503 char next = seg.first == seg.second ? next_r : -1; 1504 bool found = 0; 1505 for (int j = 0; j < 3; ++j) { 1506 if (prev == j || next == j || !rem[j]) { 1507 continue; 1508 } 1509 --rem[j]; 1510 auto cs = co(seg.second - seg.first, j, seg.second + 1 < v.size() ? idx[v[seg.second + 1]] : 3); 1511 auto vv = mk + cs; 1512 if (!vv.in(rem[0], rem[1], rem[2])) { 1513 ++rem[j]; 1514 continue; 1515 } 1516 v[seg.first++] = ydx[j]; 1517 prev = j; 1518 found = 1; 1519 break; 1520 } 1521 if (!found) { 1522 return {}; 1523 } 1524 } 1525 } 1526 return v; 1527 } 1528 1529 optional<pair<vector<array<pair<char, int>, 3>>, string>> solve(string s) { 1530 auto ww = solve_fast1(s); 1531 if (!ww || !check(*ww)) { 1532 return {}; 1533 } 1534 return pair{solve_str(*ww), *ww}; 1535 } 1536 1537 signed main() { 1538 ios::sync_with_stdio(0); 1539 cin.tie(0); 1540 cout.tie(0); 1541 idx['Y'] = 0; 1542 idx['D'] = 1; 1543 idx['X'] = 2; 1544 idx['?'] = 99; 1545 int t; 1546 cin >> t; 1547 while (t--) { 1548 string s; 1549 cin >> s; 1550 auto r = solve(s); 1551 if (r) { 1552 cout << "YES\n" << r->second << "\n"; 1553 for (auto &x: r->first) { 1554 for (auto &e: x) { 1555 cout << e.first << " " << e.second << " "; 1556 } 1557 cout << "\n"; 1558 } 1559 } else { 1560 cout << "NO\n"; 1561 } 1562 } 1563 } 1564 ```