1936.md (63909B)
1 Source: https://codeforces.com/blog/entry/126513 2 3 Thank you for participation and we hope you enjoy this round :) 4 5 #### [D2A — Shuffle Party](https://codeforces.com/contest/1937/problem/A) 6 7 Idea : [chromate00](/profile/chromate00 "Эксперт chromate00") 8 9 **Hint (for thinkers)** 10 11 If you think in terms of $k$, it might be hard to find the solution. Maybe it will be helpful if you fix $d$ and find the $k$ which will be swapped with $d$. 12 13 **Hint (for observers)** 14 15 Try bruteforcing for, say, $n \le 20$. Do you see a pattern? 16 17 **Tutorial** 18 19 On $n=1$, the answer is trivially $1$. 20 21 On $n=2$, index $1$ and $2$ are swapped. The answer is therefore $2$. 22 23 For $n \gt 2$, let us assume the element $1$ is on index $a$ and it will be swapped with index $k$. Then, $a$ must be $k/2$. We will prove this by contradiction. Let us assume that there is no divisor greater than $a$, and $a$ is lesser than $k/2$. But then, as $a$ is a multiple of $2$ in the base condition, $k$ must be a multiple of $2$, and $k/2$ is a divisor of $k$. This contradicts the assumption. By induction we can see that $a$ is always a multiple of $2$, and this proof will always hold. The element $1$ will move only when $k/2=a$. 24 25 Therefore, we can find the largest value of $v$ such that $2^v \le n$. The answer turns out to be $2^v$. 26 27 **solution** 28 29 ``` 30 #include<bits/stdc++.h> 31 using namespace std; 32 using ll=long long; 33 34 int main() 35 { 36 cin.tie(0)->sync_with_stdio(0); 37 ll q;cin>>q; 38 while(q--) 39 { 40 ll n,p=1;cin>>n; 41 while(p*2<=n)p<<=1; 42 cout<<p<<"\n"; 43 } 44 } 45 ``` 46 47 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=lLmVzA49BRM> 48 49 #### [D2B — Binary Path](https://codeforces.com/contest/1937/problem/B) 50 51 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm") 52 53 **Hint1** 54 55 Let’s call path $(1,1) \rightarrow \ldots \rightarrow (1,i)\rightarrow(2,i) \rightarrow \ldots \rightarrow (2,n)$ the $i$-th path. What's the difference between the $i$-th path and the $(i+1)$-th path? 56 57 **Hint2** 58 59 What if $a_{2i}=1$ and $a_{1(i+1)}=0$ ? 60 61 **Hint3** 62 63 What if $a_{2i}=0$ and $a_{1(i+1)}=1$ ? 64 65 **Tutorial** 66 67 * Let the string achieved by moving down on the $i$-th column be $S_i$. Then, for any $1 \le k \lt n$, one can observe that $S_k$ and $S_{k+1}$ can only differ by at most one index, which is index $k+1$. Thus, comparing $S_k$ and $S_{k+1}$ lexicographically can be done in $O(1)$, by comparing this one index. 68 * After finding the lexicographically smallest string, counting the occurrence of this string can be done straightforwardly in $O(n)$. 69 * The implementation can differ for each participant, but the following method provides a clean implementation. Let the initial coordinate be $(1,1)$, and maintain a counter which is initially reset to $1$. Then repeat the following until we reach $(2,n)$: 70 71 1. If we are on row $2$, move to the right. 72 2. If we are on column $n$, move downwards. 73 3. From here, let the character on the right be $a$, and one below be $b$. 74 4. If $a \gt b$, move downwards. 75 5. If $a \lt b$, move to the right and reset the counter to $1$. 76 6. If $a=b$, move to the right and increment the counter. 77 78 * In the end, the string on the path we passed through will be lexicographically smallest, and the integer on the counter will be the number of occurrences. 79 80 **solution** 81 82 ``` 83 #include <map> 84 #include <set> 85 #include <cmath> 86 #include <ctime> 87 #include <queue> 88 #include <stack> 89 #include <cstdio> 90 #include <cstdlib> 91 #include <vector> 92 #include <cstring> 93 #include <algorithm> 94 #include <iostream> 95 using namespace std; 96 typedef double db; 97 typedef long long ll; 98 typedef unsigned long long ull; 99 const int N=1000010; 100 const int LOGN=28; 101 const ll TMD=0; 102 const ll INF=2147483647; 103 int T,n; 104 char a[3][N]; 105 106 int main() 107 { 108 scanf("%d",&T); 109 while(T--) 110 { 111 scanf("%d",&n); 112 for(int i=1;i<=2;i++) 113 { 114 scanf("\n"); 115 for(int j=1;j<=n;j++) 116 scanf("%c",&a[i][j]); 117 } 118 int max_down=n,min_down=1; 119 for(int i=n;i>=2;i--) 120 if(a[1][i]=='1'&&a[2][i-1]=='0') max_down=i-1; 121 for(int i=1;i<max_down;i++) 122 if(a[2][i]=='1'&&a[1][i+1]=='0') min_down=i+1; 123 for(int i=1;i<=max_down;i++) printf("%c",a[1][i]); 124 for(int i=max_down;i<=n;i++) printf("%c",a[2][i]); 125 printf("\n"); 126 printf("%d\n",max_down-min_down+1); 127 } 128 129 return 0; 130 } 131 ``` 132 133 #### [D1A — Bitwise Operation Wizard](https://codeforces.com/contest/1936/problem/A) 134 135 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm") 136 137 **Hint1** 138 139 What's the maximum value of $p_i \oplus p_j$? 140 141 **Hint2** 142 143 How to get $i$, such that $p_i = n-1$? 144 145 **Hint3** 146 147 How to get $j$, such that $p_i \oplus p_j$ reaches the maximum value? 148 149 **Tutorial** 150 151 Step1:do queries $? \ x \ x \ y \ y$ like classic searching for the maximum value among $n$ numbers to get $p_i= n-1$; 152 153 Step2:do queries $? \ x \ i \ y \ i$ to find all index $k$ such that $p_i | p_{k}$ reaches the maximum value. We store all such indexes in a vector $id$ . 154 155 Step3:do queries $? \ id[x] \ id[x] \ id[y] \ id[y]$ to find $j$ in $id$ such that $p_j$ reaches the minimum value. 156 157 **solution** 158 159 ``` 160 #include <map> 161 #include <set> 162 #include <cmath> 163 #include <ctime> 164 #include <queue> 165 #include <stack> 166 #include <cstdio> 167 #include <cstdlib> 168 #include <vector> 169 #include <cstring> 170 #include <algorithm> 171 #include <iostream> 172 using namespace std; 173 typedef double db; 174 typedef long long ll; 175 typedef unsigned long long ull; 176 const int N=1000010; 177 const int LOGN=28; 178 const ll TMD=0; 179 const ll INF=2147483647; 180 int T,n; 181 182 char query(int a,int b,int c,int d) 183 { 184 char x; 185 printf("? %d %d %d %d\n",a,b,c,d); 186 fflush(stdout); 187 cin>>x; 188 fflush(stdout); 189 return x; 190 } 191 192 int main() 193 { 194 scanf("%d",&T); 195 while(T--) 196 { 197 scanf("%d",&n); 198 int mx=0,ans1=0,ans2; 199 vector<int> v; 200 for(int i=1;i<n;i++) 201 { 202 int c=query(ans1,ans1,i,i); 203 if(c=='<') ans1=i; 204 } 205 v.push_back(0); 206 for(int i=1;i<n;i++) 207 { 208 int c=query(mx,ans1,i,ans1); 209 if(c=='<') 210 { 211 mx=i; 212 v.clear(); 213 v.push_back(i); 214 } 215 else if(c=='=') v.push_back(i); 216 } 217 ans2=v[0]; 218 for(int i=1;i<v.size();i++) 219 { 220 int c=query(ans2,ans2,v[i],v[i]); 221 if(c=='>') ans2=v[i]; 222 } 223 printf("! %d %d\n",ans1,ans2); 224 fflush(stdout); 225 } 226 227 return 0; 228 } 229 ``` 230 231 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=jfcx1Rs8I28> 232 233 #### [D1B — Pinball](https://codeforces.com/contest/1936/problem/B) 234 235 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm") 236 237 **UPD**: It conflicts with <https://codeforces.com/contest/733/problem/E>. This is a coincidence. There are no excuses. Very sorry for any inconvenience caused to everyone. 238 239 **Hint1** 240 241 Observe: which cells actually change the direction of the pinball placed at position $p$ initially? 242 243 **Hint2** 244 245 These cells are the $ \gt $ to the left of $p$ and the $ \lt $ to the right of $p$. Can you see the trace of the pinball? 246 247 **Hint3** 248 249 How to quickly calculate the time when a pinball leaves the grid? 250 251 **Tutorial** 252 253 We observe that, in fact, only the $ \gt $ to the left of $p$ and the $ \lt $ to the right of $p$ change the direction of the pinball placed at position $p$ initially. 254 255 For convenience, let's assume $s_p$ is $ \gt $, $k=min(countright(1,p),countleft(p+1,n))$, and the pinball leaves from the left boundary(for other situations, we can handle them in a similar way). 256 257 We can obtain $right[1,\ldots,k]$ and $left[1,\ldots,k]$ through prefix sum + binary search, where $right$ represents the indices of $ \gt $ to the left of $p$ (in decreasing order), and $left$ represents the indices of $ \lt $ to the right of $p$ (in increasing order). 258 259 We use $right$ and $left$ to describe the trace of the pinball: 260 261 The first segment: the pinball moves from $right_1$ to $left_1$; 262 263 The second segment: the pinball moves from $left_1$ to $right_2$; 264 265 The third segment: the pinball moves from $right_2$ to $left_3$; 266 267 $\ldots$ 268 269 The $2k$-th segment: the pinball moves from $left_k$ to the left boundary. 270 271 It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves. 272 273 **solution** 274 275 ``` 276 #include <map> 277 #include <set> 278 #include <cmath> 279 #include <ctime> 280 #include <queue> 281 #include <stack> 282 #include <cstdio> 283 #include <cstdlib> 284 #include <vector> 285 #include <cstring> 286 #include <algorithm> 287 #include <iostream> 288 using namespace std; 289 typedef double db; 290 typedef long long ll; 291 typedef unsigned long long ull; 292 const int N=1000010; 293 const int LOGN=28; 294 const ll TMD=0; 295 const ll INF=2147483647; 296 int T,n; 297 ll Sl[N],Sr[N],IDl[N],IDr[N]; 298 char s[N]; 299 300 int findpre(int x) 301 { 302 int L=0,R=n+1,M; 303 while(L+1!=R) 304 { 305 M=(L+R)>>1; 306 if(Sr[M]<x) L=M; 307 else R=M; 308 } 309 return R; 310 } 311 312 int findsuf(int x) 313 { 314 int L=0,R=n+1,M; 315 while(L+1!=R) 316 { 317 M=(L+R)>>1; 318 if(Sl[n]-Sl[M-1]<x) R=M; 319 else L=M; 320 } 321 return L; 322 } 323 324 int main() 325 { 326 scanf("%d",&T); 327 while(T--) 328 { 329 scanf("%d%s",&n,s); 330 for(int i=1;i<=n;i++) 331 { 332 Sr[i]=Sr[i-1]+(s[i-1]=='>'); 333 Sl[i]=Sl[i-1]+(s[i-1]=='<'); 334 IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 335 IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 336 } 337 for(int i=1;i<=n;i++) 338 { 339 if(s[i-1]=='>') 340 { 341 if(Sr[i]>Sl[n]-Sl[i]) 342 { 343 int p=findpre(Sr[i]-(Sl[n]-Sl[i])); 344 printf("%I64d ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1)); 345 } 346 else 347 { 348 int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1); 349 printf("%I64d ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i); 350 } 351 } 352 else 353 { 354 if(Sr[i]>=Sl[n]-Sl[i-1]) 355 { 356 int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1); 357 printf("%I64d ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1)); 358 } 359 else 360 { 361 int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]); 362 printf("%I64d ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i); 363 } 364 } 365 } 366 printf("\n"); 367 } 368 369 return 0; 370 } 371 ``` 372 373 #### [D1C — Pokémon Arena](https://codeforces.com/contest/1936/problem/C) 374 375 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm") 376 377 **Hint1** 378 379 In fact, you don't need to hire the same Pokemon more than once. 380 381 **Hint2** 382 383 Consider graph building. 384 385 **Hint3** 386 387 How to reduce the number of edges in the graph? 388 389 **Tutorial** 390 391 Let's consider $n$ Pokémon as nodes, and defeating Pokémon $u$ by Pokémon $v$ as the edge $u \rightarrow v$. Then the problem is essentially finding the shortest path from $n$ to $1$. 392 393 If we brute force to construct the graph, the time complexity will be $O(n^2m)$, which is unacceptable. How can we find a better way to build the graph? 394 395 Recalling, we need to represent all processes like "Pokémon $u$ increased attribute $x$ by some value and defeated Pokémon $v$" using paths in the graph. 396 397 We will use the following graph building to achieve this. Overall, we consider each attribute separately. For the $x$-th attribute, we construct $2n$ virtual nodes $X_1,...,X_n$ and $Y_1,...,Y_n$, and connect each Pokémon based on the $x$-th attribute. 398 399 For example, $n=3$ and $a_{1,1}=9, a_{2,1}=6, a_{3,1}=1$, we have the following graph building for attribute $1$: 400 401  402 403 In this graph,for example,"Pokémon $3$ increased attribute $1$ by $8$ and defeated Pokémon $1$" can be represented as path $3 \rightarrow X1 \rightarrow X2 \rightarrow X3 \rightarrow Y3 \rightarrow 1$. 404 405 More generally, our graph building method is : 406 407 * Consider each attribute separately. Assuming we are processing the $i$-th attribute, insert all $a_{1,i} , \ldots ,a_{n,i}$ into $val$ and sort it (for convenience, we assume that they are pairwise different). 408 * Construct $2n$ virtual nodes $X_1,...,X_n$ and $Y_1,...,Y_n$; 409 * Add edge $X_i \rightarrow X_{i+1}$ with a value of $(val_{i+1}-val_i)$ for $1 \le i \lt n$; 410 * Add edge $Y_{i+1} \rightarrow Y_{i}$ with a value of $0$ for $1 \le i \lt n$; 411 * Add edge $X_i \rightarrow Y_{i}$ with a value of $0$ for $1 \le i \le n$; 412 * Add edge $i \rightarrow X_{rank_i}$ with a value of $c_i$ for $1 \le i \le n$; 413 * Add edge $Y_{rank_i} \rightarrow i$ with a value of $0$ for $1 \le i \le n$. 414 415 Then we just run Dijkstra algorithm in this graph. The time complexity is $O(nmlog(nm))$. 416 417 **solution** 418 419 ``` 420 #include <bits/stdc++.h> 421 #define int long long 422 #define fi first 423 #define se second 424 425 using namespace std; 426 427 const int INFF = 1e18; 428 429 int32_t main() 430 { 431 ios_base::sync_with_stdio(false); 432 cin.tie(NULL); 433 434 int t; 435 cin >> t; 436 437 while (t --> 0) { 438 int n, m; 439 cin >> n >> m; 440 441 vector<int> c(n + 1); 442 for (int i = 1; i <= n; i++) cin >> c[i]; 443 444 vector<vector<int>> a(n + 1, vector<int>(m + 1)); 445 vector<vector<pair<int, int>>> b(m + 1); 446 for (int i = 1; i <= n; i++) { 447 for (int j = 1; j <= m; j++) { 448 cin >> a[i][j]; 449 450 b[j].push_back({a[i][j], i}); 451 } 452 } 453 454 vector<vector<int>> rank(n + 1, vector<int>(m + 1)); 455 vector<vector<int>> dec(n + 1, vector<int>(m + 1)); 456 for (int j = 1; j <= m; j++) { 457 sort(b[j].begin(), b[j].end()); 458 459 for (int i = 0; i < n; i++) { 460 auto [x, id] = b[j][i]; 461 rank[id][j] = i + 1; 462 dec[i + 1][j] = id; 463 } 464 } 465 466 int ans = INFF; 467 vector<int> vis(n + 1, 0); 468 vector<vector<int>> dist(n + 1, vector<int>(m + 1, INFF)); 469 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; 470 vis[1] = 1; 471 for (int j = 1; j <= m; j++) dist[1][j] = 0, pq.push({dist[1][j], 1, j}); 472 while (!pq.empty()) { 473 auto [w, x, t] = pq.top(); 474 pq.pop(); 475 476 if (dist[x][t] < w) continue; 477 478 if (x == n) ans = min(ans, w + c[n]); 479 480 if (rank[x][t] < n) { 481 int z = dec[rank[x][t] + 1][t]; 482 if (w < dist[z][t]) { 483 dist[z][t] = w; 484 pq.push({dist[z][t], z, t}); 485 } 486 } 487 488 if (rank[x][t] > 1) { 489 int z = dec[rank[x][t] - 1][t]; 490 if (w + a[x][t] - a[z][t] < dist[z][t]) { 491 dist[z][t] = w + a[x][t] - a[z][t]; 492 pq.push({dist[z][t], z, t}); 493 } 494 } 495 496 if (!vis[x]) { 497 vis[x] = 1; 498 for (int j = 1; j <= m; j++) { 499 if (w + c[x] < dist[x][j]) { 500 dist[x][j] = w + c[x]; 501 pq.push({dist[x][j], x, j}); 502 } 503 } 504 } 505 } 506 507 cout << ans << '\n'; 508 } 509 510 return 0; 511 } 512 ``` 513 514 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=ysdozposXkQ> 515 516 #### [D1D — Bitwise Paradox](https://codeforces.com/contest/1936/problem/D) 517 518 Idea : [Psychotic_D](/profile/Psychotic_D "Международный мастер Psychotic_D"), [MagicalFlower](/profile/MagicalFlower "Легендарный гроссмейстер MagicalFlower") 519 520 **Tutorial** 521 522 First we use the line segment tree to maintain sequence $b$. For the nodes $[l,r]$ on each line segment tree, we maintain the first and last occurrence positions of each binary bit in the interval. 523 524 We need to merge the two intervals, whether it is modification or query. Suppose you want to use the information of $[l, mid], [mid +1, r]$ to merge the information of $[l, r]$. Consider the answer that spans two intervals. If we want to make the $i$-th position of the interval OR $1$, then there are two possibilities 525 526 1. Select the last occurrence position $P$ of the $i$-th bit in $[l,mid].$ 527 2. Select the first occurrence position $Q$ of the $i$-th bit in $[mid+1,r].$ 528 529 Let $x = max(a[P], a[P+1],\ldots, a[mid]), y = max(a[mid + 1], a[mid + 2], \ldots, a[Q]).$ 530 531 If $x \lt =y,$ we can choose the position $P$ greedily, because his price is smaller. If you choose $Q,$ then you must also choose $P,$ because choosing $P$ does not increase max $a.$ Otherwise, select $Q$ on the contrary. 532 533 With the above greedy, then you can enumerate the first binary bit $i$ that is larger than $v$. The $i$-th bit of the interval OR must be $1$, and the $i$-th bit of $v$ is $0$. For the $j$-th $(j \gt i)$ bit, if the $j$-th bit of $v$ is $1$, then the $j$-th bit must also be $1$. The rest of the bits can be regarded as $0$ or $1$, you only need to deal with these bits that must be selected $1$ greedily, and expand the interval. 534 535 You can use the st table $O(1)$ to find the interval max of $a$, so you can merge the information of the two intervals in the time of $O(log V)$. With the line segment tree, $O(q log n log V + n log V)$ can be done. 536 537 **solution** 538 539 ``` 540 #include <bits/stdc++.h> 541 using namespace std; 542 constexpr int N = 5e5 + 10, V = 30, inf = INT_MAX, L = 18; 543 int n, q, S, a[N], b[N]; 544 struct Rmq 545 { 546 int st[L][N]; 547 void init() 548 { 549 for (int i = 1; i <= n; i++) 550 st[0][i] = a[i]; 551 for (int i = 1; i < L; i++) 552 { 553 for (int j = 1; j <= n - (1 << i) + 1; j++) 554 { 555 st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]); 556 } 557 } 558 } 559 int qry(int l, int r) 560 { 561 int k = __lg(r - l + 1); 562 return max(st[k][l], st[k][r - (1 << k) + 1]); 563 } 564 } ds; 565 struct Info 566 { 567 int pre[V], suf[V]; 568 int ans, l, r; 569 Info() 570 { 571 memset(pre, 0, sizeof(pre)); 572 memset(suf, 0, sizeof(suf)); 573 ans = inf, l = r = 0; 574 } 575 Info(const Info &x, const Info &y) 576 { 577 for (int i = 0; i < V; i++) 578 { 579 pre[i] = x.pre[i] ? x.pre[i] : y.pre[i]; 580 suf[i] = y.suf[i] ? y.suf[i] : x.suf[i]; 581 } 582 ans = inf, l = r = 0; 583 } 584 friend Info operator+(const Info &x, const Info &y) 585 { 586 Info z(x, y); 587 z.ans = min(x.ans, y.ans), z.l = x.l, z.r = y.r; 588 int pl = x.r, pr = y.l; 589 if (!pl) 590 return z; 591 for (int i = V - 1; i >= 0; i--) 592 { 593 int u = x.suf[i], v = y.pre[i]; 594 if (u) 595 u = min(u, pl); 596 if (v) 597 v = max(v, pr); 598 int lans = u ? ds.qry(u, pr) : inf; 599 int rans = v ? ds.qry(pl, v) : inf; 600 if (lans < rans) 601 { 602 if (S >> i & 1) 603 { 604 if (lans < z.ans) 605 pl = u; 606 else 607 break; 608 } 609 else 610 z.ans = min(z.ans, lans); 611 } 612 else 613 { 614 if (S >> i & 1) 615 { 616 if (rans < z.ans) 617 pr = v; 618 else 619 break; 620 } 621 else 622 z.ans = min(z.ans, rans); 623 } 624 } 625 return z; 626 } 627 void clear() 628 { 629 *this = Info(); 630 } 631 void upd(int p) 632 { 633 l = r = p, ans = b[p] > S ? a[p] : inf; 634 memset(pre, 0, sizeof(pre)); 635 memset(suf, 0, sizeof(suf)); 636 for (int j = 0; j < V; j++) 637 { 638 if (b[p] >> j & 1) 639 { 640 suf[j] = p; 641 pre[j] = p; 642 } 643 } 644 } 645 } ans; 646 void reply(const Info &cur) 647 { 648 ans = ans + cur; 649 } 650 struct Node 651 { 652 Node *ls, *rs; 653 int l, r, mid; 654 Info info; 655 void up() 656 { 657 info = ls->info + rs->info; 658 } 659 void update(int p) 660 { 661 if (l == r) 662 return info.upd(l); 663 p <= mid ? ls->update(p) : rs->update(p); 664 up(); 665 } 666 void query(int ql, int qr) 667 { 668 if (l >= ql && r <= qr) 669 return reply(info); 670 if (ql <= mid) 671 ls->query(ql, qr); 672 if (qr > mid) 673 rs->query(ql, qr); 674 } 675 } mempool[N + 5 << 1], *cnt = mempool, *rt; 676 Node *build(int l, int r) 677 { 678 Node *u = cnt++; 679 int mid = l + r >> 1; 680 u->l = l, u->r = r, u->mid = mid; 681 if (l == r) 682 { 683 u->info.upd(l); 684 return u; 685 } 686 u->ls = build(l, mid); 687 u->rs = build(mid + 1, r); 688 u->up(); 689 return u; 690 } 691 692 void solve() 693 { 694 cin >> n >> S; 695 S--; 696 for (int i = 1; i <= n; i++) 697 cin >> a[i]; 698 ds.init(); 699 for (int i = 1; i <= n; i++) 700 cin >> b[i]; 701 rt = build(1, n); 702 cin >> q; 703 for (int i = 0; i < q; i++) 704 { 705 int opt; 706 cin >> opt; 707 if (opt == 1) 708 { 709 int p, x; 710 cin >> p >> x; 711 b[p] = x; 712 rt->update(p); 713 } 714 else 715 { 716 int l, r; 717 cin >> l >> r; 718 ans.clear(); 719 rt->query(l, r); 720 cout << (ans.ans == inf ? -1 : ans.ans) << ' '; 721 } 722 } 723 cout << "\n"; 724 } 725 int main() 726 { 727 #ifndef ONLINE_JUDGE 728 freopen("input.txt", "r", stdin); 729 freopen("output.txt", "w", stdout); 730 #endif 731 ios_base::sync_with_stdio(0); 732 cin.tie(0); 733 cout.tie(0); 734 ios::sync_with_stdio(false), cin.tie(0); 735 int t = 0; 736 cin >> t; 737 while (t--) 738 { 739 solve(); 740 } 741 742 // cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n'; 743 return 0; 744 } 745 ``` 746 747 #### [D1E — Yet Yet Another Permutation Problem](https://codeforces.com/contest/1936/problem/E) 748 749 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm") 750 751 **Hint1** 752 753 We found it difficult to directly calculate all valid permutations. How about calculating all invalid permutations? 754 755 **Hint2** 756 757 Can you come up with an $O(n^2)$ DP solution? 758 759 **Hint3** 760 761 How to optimize the $O(n^2)$ DP solution? 762 763 **Tutorial** 764 765 We found it difficult to directly calculate all valid permutations. Consider calculating all invalid permutations and subtract it from $n!$. 766 767 Let's first make some notes. We note $P_i=max(p_1,...,p_i),Q_i=max(q_1,...,q_i)$,and $last_i=max(j)(P_j \neq P_i)$.And note the values of all extreme points is $val[1,...,m]$ and positions is $pos[1,...,m]$. 768 769 For example,$p=[3,1,4,2,6,5]$,we get $m=3$, $val=[3,4,6]$ and $pos=[1,3,5]$. 770 771 Let’s call a permutation $q$ “i-invalid” if there’s an index $j$ satisfying $Q_j=P_j=val_i$. 772 773 Note $S_i$ as the set of all “i-invalid” permutations.According to the Inclusion-Exclusion Principle,the answer is $n!-(|S_1|+|S_2|+...)+(|S_1∩S_2|+|S_1∩S_3|+...)-...$ 774 775 Consider put $val_i$ in $q$ to make $q$ “i-invalid”.There’re $2$ kinds of ways: 776 777 * $q_j=val_i(1 \le j \lt pos_i)$ and $Q_{pos_i}=val_i$; 778 * $q_j=val_i(pos_i \le j \lt pos_{i+1})$ and $Q_{pos_i}=val_i$. 779 780 In both cases,we call the first $max(j,pos_i)$ numbers are “determined”. In other words,they’re some numbers in $[1,val_i]$. 781 782 Then we can find an $O(n^2)$ DP. Note $dp_{i,j}$ — $i$ stands for the first $i$ numbers is “determined”,and $j$ stands for $j$ extreme values are “invalid”. In fact we only care about the parity of $j$,so $j=0,1$. Note for the first $i$ numbers are “determined” automatically means $Q_i=P_i$. In addition,$q_i=P_i(P_i=P_{i-1})$ or $q_i \lt P_i(P_i \neq P_{i-1})$. 783 784 We get a DP formula $dp_{i,j}= \Sigma_{k=0}^{last_i} dp_{k,j \oplus 1} \cdot A^{P_i-k-1}_{i-k-1} \cdot (P_i==P_{i+1}?1:i-k)$ 785 786 Here is a small trick to reduce the constant. If we note $f_i=dp_{i,0}-dp_{i,1}$, we get a more concise formula $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (P_i==P_{i+1}?1:i-j)$ 787 788 We perform the following transformation on the formula. 789 790 ① For $i$ satisfying $P_i=P_{i-1}$, we get 791 792 $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} = -[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)!$ 793 794 ② For $i$ satisfying $P_i \neq P_{i-1}$, we get 795 796 $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (i-j) = -i[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)! + [(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} jf_{j} \cdot (P_i-j-1)!$ 797 798 After that, we have transformed the formula into a classical form $f(i)= h(i) \Sigma_{j=0}^{i-1} f(j) \cdot g(i-j)$, which can be calculate in $O(n log^2 n)$ by D&C+FFT. 799 800 **solution** 801 802 ``` 803 #include<bits/stdc++.h> 804 using namespace std; 805 806 #define all(a) a.begin(),a.end() 807 #define pb push_back 808 #define sz(a) ((int)a.size()) 809 810 using ll=long long; 811 using u32=unsigned int; 812 using u64=unsigned long long; 813 using i128=__int128; 814 using u128=unsigned __int128; 815 using f128=__float128; 816 817 using pii=pair<int,int>; 818 using pll=pair<ll,ll>; 819 820 template<typename T> using vc=vector<T>; 821 template<typename T> using vvc=vc<vc<T>>; 822 template<typename T> using vvvc=vc<vvc<T>>; 823 824 using vi=vc<int>; 825 using vll=vc<ll>; 826 using vvi=vc<vi>; 827 using vvll=vc<vll>; 828 829 #define vv(type,name,n,...) \ 830 vector<vector<type>> name(n,vector<type>(__VA_ARGS__)) 831 #define vvv(type,name,n,m,...) \ 832 vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__))) 833 834 template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>; 835 template<typename T> using max_heap=priority_queue<T>; 836 837 // https://trap.jp/post/1224/ 838 #define rep1(n) for(ll i=0; i<(ll)(n); ++i) 839 #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i) 840 #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i) 841 #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c)) 842 #define cut4(a,b,c,d,e,...) e 843 #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) 844 #define per1(n) for(ll i=((ll)n)-1; i>=0; --i) 845 #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i) 846 #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i) 847 #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c)) 848 #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) 849 #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s))) 850 851 template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);} 852 template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);} 853 854 template<typename T> 855 void sort_unique(vector<T> &vec){ 856 sort(vec.begin(),vec.end()); 857 vec.resize(unique(vec.begin(),vec.end())-vec.begin()); 858 } 859 860 template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;} 861 template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;} 862 863 template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;} 864 template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;} 865 866 #ifdef i_am_noob 867 #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) 868 template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 869 template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 870 template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 871 template<typename T> void _do(T && x) {cerr << x << endl;} 872 template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} 873 #else 874 #define bug(...) 777771449 875 #endif 876 877 template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 878 template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 879 template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 880 template<typename T> void print(T && x) {cout << x << "\n";} 881 template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);} 882 883 template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;} 884 885 vvi read_graph(int n, int m, int base=1){ 886 vvi adj(n); 887 for(int i=0,u,v; i<m; ++i){ 888 cin >> u >> v,u-=base,v-=base; 889 adj[u].pb(v),adj[v].pb(u); 890 } 891 return adj; 892 } 893 894 vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);} 895 896 template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};} 897 898 template<typename T> constexpr T inf=0; 899 template<> constexpr int inf<int> = 0x3f3f3f3f; 900 template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f; 901 902 template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;} 903 904 template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;} 905 906 #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) 907 908 #include <utility> 909 910 namespace atcoder { 911 912 namespace internal { 913 914 // @param m `1 <= m` 915 // @return x mod m 916 constexpr long long safe_mod(long long x, long long m) { 917 x %= m; 918 if (x < 0) x += m; 919 return x; 920 } 921 922 // Fast modular multiplication by barrett reduction 923 // Reference: https://en.wikipedia.org/wiki/Barrett_reduction 924 // NOTE: reconsider after Ice Lake 925 struct barrett { 926 unsigned int _m; 927 unsigned long long im; 928 929 // @param m `1 <= m < 2^31` 930 barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {} 931 932 // @return m 933 unsigned int umod() const { return _m; } 934 935 // @param a `0 <= a < m` 936 // @param b `0 <= b < m` 937 // @return `a * b % m` 938 unsigned int mul(unsigned int a, unsigned int b) const { 939 // [1] m = 1 940 // a = b = im = 0, so okay 941 942 // [2] m >= 2 943 // im = ceil(2^64 / m) 944 // -> im * m = 2^64 + r (0 <= r < m) 945 // let z = a*b = c*m + d (0 <= c, d < m) 946 // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im 947 // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2 948 // ((ab * im) >> 64) == c or c + 1 949 unsigned long long z = a; 950 z *= b; 951 #ifdef _MSC_VER 952 unsigned long long x; 953 _umul128(z, im, &x); 954 #else 955 unsigned long long x = 956 (unsigned long long)(((unsigned __int128)(z)*im) >> 64); 957 #endif 958 unsigned int v = (unsigned int)(z - x * _m); 959 if (_m <= v) v += _m; 960 return v; 961 } 962 }; 963 964 // @param n `0 <= n` 965 // @param m `1 <= m` 966 // @return `(x ** n) % m` 967 constexpr long long pow_mod_constexpr(long long x, long long n, int m) { 968 if (m == 1) return 0; 969 unsigned int _m = (unsigned int)(m); 970 unsigned long long r = 1; 971 unsigned long long y = safe_mod(x, m); 972 while (n) { 973 if (n & 1) r = (r * y) % _m; 974 y = (y * y) % _m; 975 n >>= 1; 976 } 977 return r; 978 } 979 980 // Reference: 981 // M. Forisek and J. Jancina, 982 // Fast Primality Testing for Integers That Fit into a Machine Word 983 // @param n `0 <= n` 984 constexpr bool is_prime_constexpr(int n) { 985 if (n <= 1) return false; 986 if (n == 2 || n == 7 || n == 61) return true; 987 if (n % 2 == 0) return false; 988 long long d = n - 1; 989 while (d % 2 == 0) d /= 2; 990 constexpr long long bases[3] = {2, 7, 61}; 991 for (long long a : bases) { 992 long long t = d; 993 long long y = pow_mod_constexpr(a, t, n); 994 while (t != n - 1 && y != 1 && y != n - 1) { 995 y = y * y % n; 996 t <<= 1; 997 } 998 if (y != n - 1 && t % 2 == 0) { 999 return false; 1000 } 1001 } 1002 return true; 1003 } 1004 template <int n> constexpr bool is_prime = is_prime_constexpr(n); 1005 1006 // @param b `1 <= b` 1007 // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g 1008 constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) { 1009 a = safe_mod(a, b); 1010 if (a == 0) return {b, 0}; 1011 1012 // Contracts: 1013 // [1] s - m0 * a = 0 (mod b) 1014 // [2] t - m1 * a = 0 (mod b) 1015 // [3] s * |m1| + t * |m0| <= b 1016 long long s = b, t = a; 1017 long long m0 = 0, m1 = 1; 1018 1019 while (t) { 1020 long long u = s / t; 1021 s -= t * u; 1022 m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b 1023 1024 // [3]: 1025 // (s - t * u) * |m1| + t * |m0 - m1 * u| 1026 // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u) 1027 // = s * |m1| + t * |m0| <= b 1028 1029 auto tmp = s; 1030 s = t; 1031 t = tmp; 1032 tmp = m0; 1033 m0 = m1; 1034 m1 = tmp; 1035 } 1036 // by [3]: |m0| <= b/g 1037 // by g != b: |m0| < b/g 1038 if (m0 < 0) m0 += b / s; 1039 return {s, m0}; 1040 } 1041 1042 // Compile time primitive root 1043 // @param m must be prime 1044 // @return primitive root (and minimum in now) 1045 constexpr int primitive_root_constexpr(int m) { 1046 if (m == 2) return 1; 1047 if (m == 167772161) return 3; 1048 if (m == 469762049) return 3; 1049 if (m == 754974721) return 11; 1050 if (m == 998244353) return 3; 1051 int divs[20] = {}; 1052 divs[0] = 2; 1053 int cnt = 1; 1054 int x = (m - 1) / 2; 1055 while (x % 2 == 0) x /= 2; 1056 for (int i = 3; (long long)(i)*i <= x; i += 2) { 1057 if (x % i == 0) { 1058 divs[cnt++] = i; 1059 while (x % i == 0) { 1060 x /= i; 1061 } 1062 } 1063 } 1064 if (x > 1) { 1065 divs[cnt++] = x; 1066 } 1067 for (int g = 2;; g++) { 1068 bool ok = true; 1069 for (int i = 0; i < cnt; i++) { 1070 if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) { 1071 ok = false; 1072 break; 1073 } 1074 } 1075 if (ok) return g; 1076 } 1077 } 1078 template <int m> constexpr int primitive_root = primitive_root_constexpr(m); 1079 1080 } // namespace internal 1081 1082 } // namespace atcoder 1083 1084 #include <cassert> 1085 #include <numeric> 1086 #include <type_traits> 1087 1088 namespace atcoder { 1089 1090 namespace internal { 1091 1092 #ifndef _MSC_VER 1093 template <class T> 1094 using is_signed_int128 = 1095 typename std::conditional<std::is_same<T, __int128_t>::value || 1096 std::is_same<T, __int128>::value, 1097 std::true_type, 1098 std::false_type>::type; 1099 1100 template <class T> 1101 using is_unsigned_int128 = 1102 typename std::conditional<std::is_same<T, __uint128_t>::value || 1103 std::is_same<T, unsigned __int128>::value, 1104 std::true_type, 1105 std::false_type>::type; 1106 1107 template <class T> 1108 using make_unsigned_int128 = 1109 typename std::conditional<std::is_same<T, __int128_t>::value, 1110 __uint128_t, 1111 unsigned __int128>; 1112 1113 template <class T> 1114 using is_integral = typename std::conditional<std::is_integral<T>::value || 1115 is_signed_int128<T>::value || 1116 is_unsigned_int128<T>::value, 1117 std::true_type, 1118 std::false_type>::type; 1119 1120 template <class T> 1121 using is_signed_int = typename std::conditional<(is_integral<T>::value && 1122 std::is_signed<T>::value) || 1123 is_signed_int128<T>::value, 1124 std::true_type, 1125 std::false_type>::type; 1126 1127 template <class T> 1128 using is_unsigned_int = 1129 typename std::conditional<(is_integral<T>::value && 1130 std::is_unsigned<T>::value) || 1131 is_unsigned_int128<T>::value, 1132 std::true_type, 1133 std::false_type>::type; 1134 1135 template <class T> 1136 using to_unsigned = typename std::conditional< 1137 is_signed_int128<T>::value, 1138 make_unsigned_int128<T>, 1139 typename std::conditional<std::is_signed<T>::value, 1140 std::make_unsigned<T>, 1141 std::common_type<T>>::type>::type; 1142 1143 #else 1144 1145 template <class T> using is_integral = typename std::is_integral<T>; 1146 1147 template <class T> 1148 using is_signed_int = 1149 typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, 1150 std::true_type, 1151 std::false_type>::type; 1152 1153 template <class T> 1154 using is_unsigned_int = 1155 typename std::conditional<is_integral<T>::value && 1156 std::is_unsigned<T>::value, 1157 std::true_type, 1158 std::false_type>::type; 1159 1160 template <class T> 1161 using to_unsigned = typename std::conditional<is_signed_int<T>::value, 1162 std::make_unsigned<T>, 1163 std::common_type<T>>::type; 1164 1165 #endif 1166 1167 template <class T> 1168 using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>; 1169 1170 template <class T> 1171 using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>; 1172 1173 template <class T> using to_unsigned_t = typename to_unsigned<T>::type; 1174 1175 } // namespace internal 1176 1177 } // namespace atcoder 1178 1179 #include <cassert> 1180 #include <numeric> 1181 #include <type_traits> 1182 1183 #ifdef _MSC_VER 1184 #include <intrin.h> 1185 #endif 1186 1187 namespace atcoder { 1188 1189 namespace internal { 1190 1191 struct modint_base {}; 1192 struct static_modint_base : modint_base {}; 1193 1194 template <class T> using is_modint = std::is_base_of<modint_base, T>; 1195 template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>; 1196 1197 } // namespace internal 1198 1199 template <int m, std::enable_if_t<(1 <= m)>* = nullptr> 1200 struct static_modint : internal::static_modint_base { 1201 using mint = static_modint; 1202 1203 public: 1204 static constexpr int mod() { return m; } 1205 static mint raw(int v) { 1206 mint x; 1207 x._v = v; 1208 return x; 1209 } 1210 1211 static_modint() : _v(0) {} 1212 template <class T, internal::is_signed_int_t<T>* = nullptr> 1213 static_modint(T v) { 1214 long long x = (long long)(v % (long long)(umod())); 1215 if (x < 0) x += umod(); 1216 _v = (unsigned int)(x); 1217 } 1218 template <class T, internal::is_unsigned_int_t<T>* = nullptr> 1219 static_modint(T v) { 1220 _v = (unsigned int)(v % umod()); 1221 } 1222 static_modint(bool v) { _v = ((unsigned int)(v) % umod()); } 1223 1224 unsigned int val() const { return _v; } 1225 1226 mint& operator++() { 1227 _v++; 1228 if (_v == umod()) _v = 0; 1229 return *this; 1230 } 1231 mint& operator--() { 1232 if (_v == 0) _v = umod(); 1233 _v--; 1234 return *this; 1235 } 1236 mint operator++(int) { 1237 mint result = *this; 1238 ++*this; 1239 return result; 1240 } 1241 mint operator--(int) { 1242 mint result = *this; 1243 --*this; 1244 return result; 1245 } 1246 1247 mint& operator+=(const mint& rhs) { 1248 _v += rhs._v; 1249 if (_v >= umod()) _v -= umod(); 1250 return *this; 1251 } 1252 mint& operator-=(const mint& rhs) { 1253 _v -= rhs._v; 1254 if (_v >= umod()) _v += umod(); 1255 return *this; 1256 } 1257 mint& operator*=(const mint& rhs) { 1258 unsigned long long z = _v; 1259 z *= rhs._v; 1260 _v = (unsigned int)(z % umod()); 1261 return *this; 1262 } 1263 mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); } 1264 1265 mint operator+() const { return *this; } 1266 mint operator-() const { return mint() - *this; } 1267 1268 mint pow(long long n) const { 1269 assert(0 <= n); 1270 mint x = *this, r = 1; 1271 while (n) { 1272 if (n & 1) r *= x; 1273 x *= x; 1274 n >>= 1; 1275 } 1276 return r; 1277 } 1278 mint inv() const { 1279 if (prime) { 1280 assert(_v); 1281 return pow(umod() - 2); 1282 } else { 1283 auto eg = internal::inv_gcd(_v, m); 1284 assert(eg.first == 1); 1285 return eg.second; 1286 } 1287 } 1288 1289 friend mint operator+(const mint& lhs, const mint& rhs) { 1290 return mint(lhs) += rhs; 1291 } 1292 friend mint operator-(const mint& lhs, const mint& rhs) { 1293 return mint(lhs) -= rhs; 1294 } 1295 friend mint operator*(const mint& lhs, const mint& rhs) { 1296 return mint(lhs) *= rhs; 1297 } 1298 friend mint operator/(const mint& lhs, const mint& rhs) { 1299 return mint(lhs) /= rhs; 1300 } 1301 friend bool operator==(const mint& lhs, const mint& rhs) { 1302 return lhs._v == rhs._v; 1303 } 1304 friend bool operator!=(const mint& lhs, const mint& rhs) { 1305 return lhs._v != rhs._v; 1306 } 1307 1308 private: 1309 unsigned int _v; 1310 static constexpr unsigned int umod() { return m; } 1311 static constexpr bool prime = internal::is_prime<m>; 1312 }; 1313 1314 template <int id> struct dynamic_modint : internal::modint_base { 1315 using mint = dynamic_modint; 1316 1317 public: 1318 static int mod() { return (int)(bt.umod()); } 1319 static void set_mod(int m) { 1320 assert(1 <= m); 1321 bt = internal::barrett(m); 1322 } 1323 static mint raw(int v) { 1324 mint x; 1325 x._v = v; 1326 return x; 1327 } 1328 1329 dynamic_modint() : _v(0) {} 1330 template <class T, internal::is_signed_int_t<T>* = nullptr> 1331 dynamic_modint(T v) { 1332 long long x = (long long)(v % (long long)(mod())); 1333 if (x < 0) x += mod(); 1334 _v = (unsigned int)(x); 1335 } 1336 template <class T, internal::is_unsigned_int_t<T>* = nullptr> 1337 dynamic_modint(T v) { 1338 _v = (unsigned int)(v % mod()); 1339 } 1340 dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); } 1341 1342 unsigned int val() const { return _v; } 1343 1344 mint& operator++() { 1345 _v++; 1346 if (_v == umod()) _v = 0; 1347 return *this; 1348 } 1349 mint& operator--() { 1350 if (_v == 0) _v = umod(); 1351 _v--; 1352 return *this; 1353 } 1354 mint operator++(int) { 1355 mint result = *this; 1356 ++*this; 1357 return result; 1358 } 1359 mint operator--(int) { 1360 mint result = *this; 1361 --*this; 1362 return result; 1363 } 1364 1365 mint& operator+=(const mint& rhs) { 1366 _v += rhs._v; 1367 if (_v >= umod()) _v -= umod(); 1368 return *this; 1369 } 1370 mint& operator-=(const mint& rhs) { 1371 _v += mod() - rhs._v; 1372 if (_v >= umod()) _v -= umod(); 1373 return *this; 1374 } 1375 mint& operator*=(const mint& rhs) { 1376 _v = bt.mul(_v, rhs._v); 1377 return *this; 1378 } 1379 mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); } 1380 1381 mint operator+() const { return *this; } 1382 mint operator-() const { return mint() - *this; } 1383 1384 mint pow(long long n) const { 1385 assert(0 <= n); 1386 mint x = *this, r = 1; 1387 while (n) { 1388 if (n & 1) r *= x; 1389 x *= x; 1390 n >>= 1; 1391 } 1392 return r; 1393 } 1394 mint inv() const { 1395 auto eg = internal::inv_gcd(_v, mod()); 1396 assert(eg.first == 1); 1397 return eg.second; 1398 } 1399 1400 friend mint operator+(const mint& lhs, const mint& rhs) { 1401 return mint(lhs) += rhs; 1402 } 1403 friend mint operator-(const mint& lhs, const mint& rhs) { 1404 return mint(lhs) -= rhs; 1405 } 1406 friend mint operator*(const mint& lhs, const mint& rhs) { 1407 return mint(lhs) *= rhs; 1408 } 1409 friend mint operator/(const mint& lhs, const mint& rhs) { 1410 return mint(lhs) /= rhs; 1411 } 1412 friend bool operator==(const mint& lhs, const mint& rhs) { 1413 return lhs._v == rhs._v; 1414 } 1415 friend bool operator!=(const mint& lhs, const mint& rhs) { 1416 return lhs._v != rhs._v; 1417 } 1418 1419 private: 1420 unsigned int _v; 1421 static internal::barrett bt; 1422 static unsigned int umod() { return bt.umod(); } 1423 }; 1424 template <int id> internal::barrett dynamic_modint<id>::bt = 998244353; 1425 1426 using modint998244353 = static_modint<998244353>; 1427 using modint1000000007 = static_modint<1000000007>; 1428 using modint = dynamic_modint<-1>; 1429 1430 namespace internal { 1431 1432 template <class T> 1433 using is_static_modint = std::is_base_of<internal::static_modint_base, T>; 1434 1435 template <class T> 1436 using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>; 1437 1438 template <class> struct is_dynamic_modint : public std::false_type {}; 1439 template <int id> 1440 struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {}; 1441 1442 template <class T> 1443 using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>; 1444 1445 } // namespace internal 1446 1447 } // namespace atcoder 1448 1449 #include <algorithm> 1450 #include <array> 1451 1452 #ifdef _MSC_VER 1453 #include <intrin.h> 1454 #endif 1455 1456 namespace atcoder { 1457 1458 namespace internal { 1459 1460 // @param n `0 <= n` 1461 // @return minimum non-negative `x` s.t. `n <= 2**x` 1462 int ceil_pow2(int n) { 1463 int x = 0; 1464 while ((1U << x) < (unsigned int)(n)) x++; 1465 return x; 1466 } 1467 1468 // @param n `1 <= n` 1469 // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` 1470 int bsf(unsigned int n) { 1471 #ifdef _MSC_VER 1472 unsigned long index; 1473 _BitScanForward(&index, n); 1474 return index; 1475 #else 1476 return __builtin_ctz(n); 1477 #endif 1478 } 1479 1480 } // namespace internal 1481 1482 } // namespace atcoder 1483 1484 #include <cassert> 1485 #include <type_traits> 1486 #include <vector> 1487 1488 namespace atcoder { 1489 1490 namespace internal { 1491 1492 template <class mint, internal::is_static_modint_t<mint>* = nullptr> 1493 void butterfly(std::vector<mint>& a) { 1494 static constexpr int g = internal::primitive_root<mint::mod()>; 1495 int n = int(a.size()); 1496 int h = internal::ceil_pow2(n); 1497 1498 static bool first = true; 1499 static mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i] 1500 if (first) { 1501 first = false; 1502 mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1 1503 int cnt2 = bsf(mint::mod() - 1); 1504 mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv(); 1505 for (int i = cnt2; i >= 2; i--) { 1506 // e^(2^i) == 1 1507 es[i - 2] = e; 1508 ies[i - 2] = ie; 1509 e *= e; 1510 ie *= ie; 1511 } 1512 mint now = 1; 1513 for (int i = 0; i <= cnt2 - 2; i++) { 1514 sum_e[i] = es[i] * now; 1515 now *= ies[i]; 1516 } 1517 } 1518 for (int ph = 1; ph <= h; ph++) { 1519 int w = 1 << (ph - 1), p = 1 << (h - ph); 1520 mint now = 1; 1521 for (int s = 0; s < w; s++) { 1522 int offset = s << (h - ph + 1); 1523 for (int i = 0; i < p; i++) { 1524 auto l = a[i + offset]; 1525 auto r = a[i + offset + p] * now; 1526 a[i + offset] = l + r; 1527 a[i + offset + p] = l - r; 1528 } 1529 now *= sum_e[bsf(~(unsigned int)(s))]; 1530 } 1531 } 1532 } 1533 1534 template <class mint, internal::is_static_modint_t<mint>* = nullptr> 1535 void butterfly_inv(std::vector<mint>& a) { 1536 static constexpr int g = internal::primitive_root<mint::mod()>; 1537 int n = int(a.size()); 1538 int h = internal::ceil_pow2(n); 1539 1540 static bool first = true; 1541 static mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i] 1542 if (first) { 1543 first = false; 1544 mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1 1545 int cnt2 = bsf(mint::mod() - 1); 1546 mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv(); 1547 for (int i = cnt2; i >= 2; i--) { 1548 // e^(2^i) == 1 1549 es[i - 2] = e; 1550 ies[i - 2] = ie; 1551 e *= e; 1552 ie *= ie; 1553 } 1554 mint now = 1; 1555 for (int i = 0; i <= cnt2 - 2; i++) { 1556 sum_ie[i] = ies[i] * now; 1557 now *= es[i]; 1558 } 1559 } 1560 1561 for (int ph = h; ph >= 1; ph--) { 1562 int w = 1 << (ph - 1), p = 1 << (h - ph); 1563 mint inow = 1; 1564 for (int s = 0; s < w; s++) { 1565 int offset = s << (h - ph + 1); 1566 for (int i = 0; i < p; i++) { 1567 auto l = a[i + offset]; 1568 auto r = a[i + offset + p]; 1569 a[i + offset] = l + r; 1570 a[i + offset + p] = 1571 (unsigned long long)(mint::mod() + l.val() - r.val()) * 1572 inow.val(); 1573 } 1574 inow *= sum_ie[bsf(~(unsigned int)(s))]; 1575 } 1576 } 1577 } 1578 1579 } // namespace internal 1580 1581 template <class mint, internal::is_static_modint_t<mint>* = nullptr> 1582 std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) { 1583 int n = int(a.size()), m = int(b.size()); 1584 if (!n || !m) return {}; 1585 if (std::min(n, m) <= 60) { 1586 if (n < m) { 1587 std::swap(n, m); 1588 std::swap(a, b); 1589 } 1590 std::vector<mint> ans(n + m - 1); 1591 for (int i = 0; i < n; i++) { 1592 for (int j = 0; j < m; j++) { 1593 ans[i + j] += a[i] * b[j]; 1594 } 1595 } 1596 return ans; 1597 } 1598 int z = 1 << internal::ceil_pow2(n + m - 1); 1599 a.resize(z); 1600 internal::butterfly(a); 1601 b.resize(z); 1602 internal::butterfly(b); 1603 for (int i = 0; i < z; i++) { 1604 a[i] *= b[i]; 1605 } 1606 internal::butterfly_inv(a); 1607 a.resize(n + m - 1); 1608 mint iz = mint(z).inv(); 1609 for (int i = 0; i < n + m - 1; i++) a[i] *= iz; 1610 return a; 1611 } 1612 1613 template <unsigned int mod = 998244353, 1614 class T, 1615 std::enable_if_t<internal::is_integral<T>::value>* = nullptr> 1616 std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) { 1617 int n = int(a.size()), m = int(b.size()); 1618 if (!n || !m) return {}; 1619 1620 using mint = static_modint<mod>; 1621 std::vector<mint> a2(n), b2(m); 1622 for (int i = 0; i < n; i++) { 1623 a2[i] = mint(a[i]); 1624 } 1625 for (int i = 0; i < m; i++) { 1626 b2[i] = mint(b[i]); 1627 } 1628 auto c2 = convolution(move(a2), move(b2)); 1629 std::vector<T> c(n + m - 1); 1630 for (int i = 0; i < n + m - 1; i++) { 1631 c[i] = c2[i].val(); 1632 } 1633 return c; 1634 } 1635 1636 std::vector<long long> convolution_ll(const std::vector<long long>& a, 1637 const std::vector<long long>& b) { 1638 int n = int(a.size()), m = int(b.size()); 1639 if (!n || !m) return {}; 1640 1641 static constexpr unsigned long long MOD1 = 754974721; // 2^24 1642 static constexpr unsigned long long MOD2 = 167772161; // 2^25 1643 static constexpr unsigned long long MOD3 = 469762049; // 2^26 1644 static constexpr unsigned long long M2M3 = MOD2 * MOD3; 1645 static constexpr unsigned long long M1M3 = MOD1 * MOD3; 1646 static constexpr unsigned long long M1M2 = MOD1 * MOD2; 1647 static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3; 1648 1649 static constexpr unsigned long long i1 = 1650 internal::inv_gcd(MOD2 * MOD3, MOD1).second; 1651 static constexpr unsigned long long i2 = 1652 internal::inv_gcd(MOD1 * MOD3, MOD2).second; 1653 static constexpr unsigned long long i3 = 1654 internal::inv_gcd(MOD1 * MOD2, MOD3).second; 1655 1656 auto c1 = convolution<MOD1>(a, b); 1657 auto c2 = convolution<MOD2>(a, b); 1658 auto c3 = convolution<MOD3>(a, b); 1659 1660 std::vector<long long> c(n + m - 1); 1661 for (int i = 0; i < n + m - 1; i++) { 1662 unsigned long long x = 0; 1663 x += (c1[i] * i1) % MOD1 * M2M3; 1664 x += (c2[i] * i2) % MOD2 * M1M3; 1665 x += (c3[i] * i3) % MOD3 * M1M2; 1666 // B = 2^63, -B <= x, r(real value) < B 1667 // (x, x - M, x - 2M, or x - 3M) = r (mod 2B) 1668 // r = c1[i] (mod MOD1) 1669 // focus on MOD1 1670 // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B) 1671 // r = x, 1672 // x - M' + (0 or 2B), 1673 // x - 2M' + (0, 2B or 4B), 1674 // x - 3M' + (0, 2B, 4B or 6B) (without mod!) 1675 // (r - x) = 0, (0) 1676 // - M' + (0 or 2B), (1) 1677 // -2M' + (0 or 2B or 4B), (2) 1678 // -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1) 1679 // we checked that 1680 // ((1) mod MOD1) mod 5 = 2 1681 // ((2) mod MOD1) mod 5 = 3 1682 // ((3) mod MOD1) mod 5 = 4 1683 long long diff = 1684 c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1)); 1685 if (diff < 0) diff += MOD1; 1686 static constexpr unsigned long long offset[5] = { 1687 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3}; 1688 x -= offset[diff % 5]; 1689 c[i] = x; 1690 } 1691 1692 return c; 1693 } 1694 1695 } // namespace atcoder 1696 1697 using namespace atcoder; 1698 1699 using mint=modint998244353; 1700 //using mint=modint1000000007; 1701 1702 template<int mod> 1703 struct nCr{ 1704 vector<static_modint<mod>> fac,inv,ifac; 1705 void calc(int n){ 1706 fac.resize(n+1),inv.resize(n+1),ifac.resize(n+1); 1707 fac[0]=inv[1]=ifac[0]=1; 1708 for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*static_modint<mod>::raw(i); 1709 for(int i=2; i<=n; ++i) inv[i]=inv[mod%i]*static_modint<mod>::raw(mod-mod/i); 1710 for(int i=1; i<=n; ++i) ifac[i]=ifac[i-1]*inv[i]; 1711 } 1712 static_modint<mod> C(int n, int m){ 1713 if(m<0||m>n) return 0; 1714 return fac[n]*ifac[m]*ifac[n-m]; 1715 } 1716 }; 1717 1718 nCr<998244353> de; 1719 1720 void ahcorz(){ 1721 // (a_i - j)! / (a_i - i)! (a_i = a_j) 1722 // (a_i - j - 1)! / (a_i - i)! * (i - j) (a_i != a_j) 1723 int n; cin >> n; 1724 de.calc(n+1); 1725 vi a; a.pb(0); 1726 rep(n){ 1727 int x; cin >> x; 1728 a.pb(max(a.back(),x)); 1729 } 1730 vc<mint> dp(n+1),aux(n+1); 1731 auto solve=[&](auto &self, int l, int r) -> void{ 1732 if(l+1==r){ 1733 if(l==0) dp[l]=-1; 1734 else dp[l]+=aux[l]*l; 1735 dp[l]*=de.ifac[a[l]-l]; 1736 return; 1737 } 1738 int mid=l+r>>1; 1739 self(self,l,mid); 1740 if(a[mid]==a[mid-1]){ 1741 int x=mid-1,y=mid; 1742 while(x-1>=l&&a[x-1]==a[mid]) x--; 1743 while(y+1<r&&a[y+1]==a[mid]) y++; 1744 mint tot,tot1,tot2; 1745 rep(i,x,mid) tot+=dp[i]*de.fac[a[mid]-i],tot1+=dp[i]*de.fac[a[mid]-i-1],tot2+=dp[i]*de.fac[a[mid]-i-1]*i; 1746 rep(i,mid,y+1) dp[i]-=tot-(tot1*i-tot2); 1747 } 1748 vc<mint> vec; 1749 rep(i,a[mid]-mid,a[r-1]-(l+1)+1) vec.pb(de.fac[i]); 1750 vc<mint> vec1,vec2; 1751 rep(i,l,mid) vec1.pb(dp[i]),vec2.pb(dp[i]*i); 1752 auto res1=convolution(vec,vec1),res2=convolution(vec,vec2); 1753 int base=a[mid]-mid+l+1; 1754 rep(i,mid,r) if(a[i]-base>=0&&a[i]-base<sz(res1)) aux[i]-=res1[a[i]-base],dp[i]+=res2[a[i]-base]; 1755 self(self,mid,r); 1756 }; 1757 solve(solve,0,n+1); 1758 print(dp[n].val()); 1759 } 1760 1761 signed main(){ 1762 ios_base::sync_with_stdio(0),cin.tie(0); 1763 cout << fixed << setprecision(20); 1764 int t=1; 1765 cin >> t; 1766 while(t--) ahcorz(); 1767 } 1768 ``` 1769 1770 #### [D1F — Grand Finale: Circles](https://codeforces.com/contest/1936/problem/F) 1771 1772 Idea : [chromate00](/profile/chromate00 "Эксперт chromate00") 1773 1774 **UPD**: The TL was a bit too loose, and unintended solutions with $\mathcal{O}(n \log^2 (1/\epsilon))$ complexity passed during the round. For the sake of the problem itself, I suggest that you try to solve assuming a $1$ second time limit. 1775 1776 **Tutorial** 1777 1778 For a given center coordinate $(x,y)$, we can model the objective function $r=f(x,y)$ to maximize as follows. 1779 1780 $f(x,y)=\min_{1 \le i \le n} {\left({r_i-\sqrt{(x_i-x)^2+(y_i-y)^2}}\right)}$ 1781 1782 Formally, this can be modeled as follows: 1783 1784 $\begin{split} \max & \ r \\ \text{s.t.} & \ \sqrt{(x_i-x)^2+(y_i-y)^2} \le r_i-r \ \ \forall \ 1 \le i \le n \end{split}$ 1785 1786 This is a **second order cone program**. Generally, this is not as simple to solve as linear or quadratic programs. There are multiple solvers out there, but all of them are either commercial or simply unfit for use on Codeforces. And even if we use general approaches to second order cone programming, their time complexity is at least $\mathcal{O}(n^{3.5})$, so they cannot work. Almost all general approaches to convex programming do not help very much for this task also, because of the following reasons. 1787 1788 * Gradient Descent cannot work in this task. The objective function is not smooth. 1789 * Coordinate Descent also cannot work in this task for the same reason, and it is not hard to find a countercase. 1790 * Subgradient methods can solve this task, but they take $\mathcal{O}(1/\epsilon^2)$ iterations to converge. This is a very big dependency on the precision, so they take too much time. 1791 * We do not expect anyone to write Adaptive Coordinate Descent during contest time, but we still tested the PRAXIS algorithm and checked that it does not pass. 1792 * Using nested ternary searches does not help very much. The time complexity will be $\mathcal{O}(n \log^2 (1/\epsilon))$, but the constants are large due to multiple function calls and floating point operations. 1793 * Heuristics such as the Nelder-Mead method are not proven to converge. In many cases we found it not converging successfully. 1794 1795 In the editorial, we will explain a solution of expected $\mathcal{O}(n)$ time complexity, with constants depending on the number of dimensions (which is $2$ in our case). 1796 1797 First, we observe that any answer can be described as a "basis" of at most $3$ selected circles. For $k=0,1,2,3$, the basis is as follows. 1798 1799 * Case 1: $k=0$ 1800 1801 This is the case of no circles, which can be regarded as an "identity element" of bases. Some very huge circle that will enclose any given circle, for example the circle with $10^{18}$ as radius and $(0,0)$ as center, can represent this case. 1802 1803 * Case 2: $k=1$ 1804 1805 This is the case of a single circle. The circle that represents this case is the one selected circle. 1806 1807 * Case 3: $k=2$ 1808 1809 This is the case of two circles, for which the basis is the largest circle in the intersection of two circles. We can find this by choosing the center as the midpoint of the two points $A$ and $B$, where $A$ and $B$ are the points where the line segment between circle centers and the circle itself intersect. 1810 1811 * Case 4: $k=3$ 1812 1813 This is the case of three circles, and the most tricky of all four cases. It can be found as one solution to the following system of quadratic equations: 1814 1815 $(x_A-x)^2+(y_A-y)^2 = (r_A-r)^2 \\ (x_B-x)^2+(y_B-y)^2 = (r_B-r)^2 \\ (x_C-x)^2+(y_C-y)^2 = (r_C-r)^2$ 1816 1817 This can be solved algebraically. If you are used to solving geometry problems in Olympiads, you may know the [''Problem of Apollonius''](https://en.wikipedia.org/wiki/Problem_of_Apollonius). This is one special case of the problem, which is not very often mentioned because often the three circles do not intersect with each other (thus most of the time one solution for $r$ must be negative). Or if one does not know the problem, they can find that the locus of the circle center that meets with two circle edges (as in Case 3) is a conic section, precisely one side of a pair of hyperbola. By finding the intersections of two hyperbola, one can find the center of this circle. Thus, this circle can be found in $\mathcal{O}(1)$ time, with constants based on number of dimensions. 1818 1819 By the system of quadratic equations stated above, we see that there are at most $2$ solutions. It is sufficient to take the one that happens to be inside the intersection. (If there are two such solutions, take the larger one. For the current version of the data this check is not necessary, but it does not hurt to try.) Thus, for some $n \gt 3$, the bases can be represented with some $k \le 3$ circles. 1820 1821 Do note that, already, we have an $\mathcal{O}(n^3)$ solution based on this. We enumerate all possible bases, and find the smallest one out of them (since that one will be the one that satisfies the conditions). 1822 1823 Now, for some basis circle $(x,y,r)$, we can check whether some given circle $(x_i,y_i,r_i)$ is "violated" by this basis (i.e. this basis is not inside this circle) in $\mathcal{O}(1)$ by comparing the distance. We take an incremental approach. We add circles to the basis one by one, up to $3$ circles. We choose to change the basis if only the next added circle is violated by the current basis. Of course, still this takes $\mathcal{O}(n^3)$ time, and sorting the circles based on any argument will not help anyways. 1824 1825 However, adding the circles in **random order** will make it only take expected $\mathcal{O}(n)$ time. This can be analyzed by the probability that a new basis will be added. The precise analysis for the time complexity is left as a practice for the reader. 1826 1827 If you have seen the minimum enclosing circle problem, the Welzl's algorithm to solve that precise problem will seem very similar to this. In fact, the suggested algorithm itself is not very different from Welzl's algorithm. If you want, though, you may take an iterative approach instead of modifying Welzl's algorithm. Using three nested loops will do. 1828 1829 There is only two issues left. The first is the issue of numerical instability. Sometimes, due to numerical instability, the algorithm will return a NaN value. It is not that hard to solve, we can simply shuffle again and rerun the algorithm. The given time limit will be sufficient for doing this unless the constant is too big. The second is more tricky, and it is about hacks. 1830 1831 If you use a fixed seed for randomization (or time-based seeds to some extent), someone may hack you by adding an adversarial test case which makes the time complexity explode back to $\mathcal{O}(n^3)$. This is very bad. How do we solve this? To intervent this, we will make the algorithm halt when the number of iterations exceed a certain limit. Formally, let us choose a constant $c$, and the algorithm will halt and rerun when the number of iterations exceeds $c \cdot n$. Then, if the probability of the algorithm successfully running in this number of iterations is $p$, the expected number of reruns needed is $\mathcal{O}(1/p)$, and hacking is much harder. The algorithm will successfully find the solution in $\mathcal{O}((c/p) \cdot n)$ time. Of course, the probability $p$ depends on $c$, and you must tune the value as needed. Empirically $c=30$ runs very well, almost always taking no longer than $0.4$ seconds under proper optimizations, and $1.5$ seconds without. 1832 1833 **solution** 1834 1835 ``` 1836 #include<bits/stdc++.h> 1837 using namespace std; 1838 using ll=long long; 1839 1840 using lf=long double; 1841 using pt=pair<lf,lf>; 1842 lf& real(pt& p){return p.first;} 1843 lf& imag(pt& p){return p.second;} 1844 pt midp(pt a,pt b){return pt{(real(a)+real(b))/2,(imag(a)+imag(b))/2};} 1845 pt addi(pt a,pt b){return pt{(real(a)+real(b)),(imag(a)+imag(b))};} 1846 pt subt(pt a,pt b){return pt{(real(a)-real(b)),(imag(a)-imag(b))};} 1847 pt mult(pt a,lf b){return pt{real(a)*b,imag(a)*b};} 1848 lf abs(pt a){return sqrtl(powl(real(a),2)+powl(imag(a),2));} 1849 lf dist(pt a,pt b){return sqrtl(powl(real(a)-real(b),2)+powl(imag(a)-imag(b),2));} 1850 1851 struct circ{pt p;lf r;}; 1852 const lf inf=1e18; 1853 1854 circ basis0(){return {pt{0,0},inf};} 1855 1856 circ basis1(circ a){return a;} 1857 1858 circ basis2(circ a,circ b) 1859 { 1860 pt aa=a.p,bb=b.p; 1861 pt ab=subt(bb,aa),ba=subt(aa,bb); 1862 lf aab=abs(ab),aba=abs(ba); 1863 real(ab)/=aab; 1864 imag(ab)/=aab; 1865 real(ba)/=aba; 1866 imag(ba)/=aba; 1867 pt ar=addi(aa,mult(ab,a.r)),br=addi(bb,mult(ba,b.r)); 1868 1869 return {midp(ar,br),dist(ar,br)/2.0L}; 1870 } 1871 1872 circ basis3(circ a,circ b,circ c) 1873 { 1874 lf x1=real(a.p),y1=imag(a.p),r1=a.r; 1875 lf x2=real(b.p),y2=imag(b.p),r2=b.r; 1876 lf x3=real(c.p),y3=imag(c.p),r3=c.r; 1877 lf a2=x1-x2,a3=x1-x3,b2=y1-y2,b3=y1-y3,c2=r2-r1,c3=r3-r1; 1878 lf d1=x1*x1+y1*y1-r1*r1,d2=d1-x2*x2-y2*y2+r2*r2,d3=d1-x3*x3-y3*y3+r3*r3; 1879 lf ab=a3*b2-a2*b3; 1880 lf xa=(b2*d3-b3*d2)/(ab*2)-x1; 1881 lf xb=(b3*c2-b2*c3)/ab; 1882 lf ya=(a3*d2-a2*d3)/(ab*2)-y1; 1883 lf yb=(a2*c3-a3*c2)/ab; 1884 lf A=xb*xb+yb*yb-1; 1885 lf B=2*(r1+xa*xb+ya*yb); 1886 lf C=xa*xa+ya*ya-r1*r1; 1887 lf r=-(A?(B-sqrtl(B*B-4*A*C))/(2*A):C/B); 1888 return {pt{x1+xa+xb*r,y1+ya+yb*r},r}; 1889 } 1890 1891 bool viol(circ p,circ a) 1892 { 1893 return a.r<p.r+dist(a.p,p.p); 1894 } 1895 1896 circ solve(vector<circ>&v) 1897 { 1898 lf _nan=nan("aaa"); 1899 mt19937_64 mt(1999999); 1900 //shuffle(begin(v),end(v),mt); 1901 vector<circ>basis; 1902 auto trivial=[&]() 1903 { 1904 if(size(basis)==0)return basis0(); 1905 if(size(basis)==1)return basis[0]; 1906 if(size(basis)==2)return basis2(basis[0],basis[1]); 1907 return basis3(basis[0],basis[1],basis[2]); 1908 }; 1909 1910 int counter=0; 1911 1912 auto rec=[&](auto rec,int n)->circ 1913 { 1914 if(n==0||size(basis)==3)return trivial(); 1915 counter++; 1916 if(counter>30*size(v))return {pt{0,0},_nan}; 1917 auto c=rec(rec,n-1); 1918 auto p=v[n-1]; 1919 if(!viol(c,p)||isnan(c.r))return c; 1920 basis.push_back(p); 1921 c=rec(rec,n-1); 1922 basis.pop_back(); 1923 return c; 1924 }; 1925 auto c=rec(rec,size(v)); 1926 while(isnan(c.r)) 1927 { 1928 counter=0; 1929 shuffle(begin(v),end(v),mt); 1930 c=rec(rec,size(v)); 1931 } 1932 return c; 1933 } 1934 1935 int main() 1936 { 1937 cin.tie(0)->sync_with_stdio(0); 1938 int n;cin>>n; 1939 vector<circ>v(n); 1940 for(auto&[p,r]:v) 1941 { 1942 ll x,y,rr;cin>>x>>y>>rr; 1943 p={x,y};r=rr; 1944 } 1945 auto ans=solve(v); 1946 cout<<setprecision(16)<<fixed<<real(ans.p)<<" "<<imag(ans.p)<<" "<<ans.r<<"\n"; 1947 } 1948 ```