codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1617.md (20523B)


      1 Source: https://codeforces.com/blog/entry/97920
      2 
      3 Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.
      4 
      5 **UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.
      6 
      7 **UPD2:** Rejudge done, the round remains rated.
      8 
      9 **Statistics**
     10 
     11 Number of FST for rated participants:
     12 
     13 * Problem A: $29$
     14 * Problem B: $90$
     15 * Problem C: $12$
     16 * Problem D1: $4$
     17 * Problem D2: $0$
     18 * Problem E: $6$
     19 
     20 Number of AK: $22$
     21 
     22 Number of clarifications: $85$
     23 
     24 [1617A - Forbidden Subsequence](/contest/1617/problem/A "Codeforces Round 761 (Div. 2)")
     25 
     26 **Hint**
     27 
     28 When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer?
     29 
     30 **Solution**
     31 
     32 If there are no occurrences of `a`, `b` or `c` in $S$, sort $S$ and output it.
     33 
     34 Else, if $T \ne$ `abc`, sort $S$ and output it.
     35 
     36 Else, output all `a`, then all `c`, then all `b`, then the rest of the string sorted.
     37 
     38 **Implementation (C++, I_Love_YrNameCouldBeHere)**
     39 
     40 ```
     41 #include <bits/stdc++.h>
     42 using namespace std;
     43 #define all(x) x.begin(), x.end()
     44 int main() {
     45     int T;
     46     cin >> T;
     47     while(T--) {
     48         string s, t;
     49         cin >> s >> t;
     50         sort(all(s));
     51         vector<int> cnt(26, 0);
     52         for(auto x: s)cnt[x - 'a']++;
     53         if(t != "abc" || !cnt[0] || !cnt[1] || !cnt[2])cout << s << "\n";
     54         else{
     55             while(cnt[0]--)cout<<"a";
     56             while(cnt[2]--)cout<<"c";
     57             while(cnt[1]--)cout<<"b";
     58             for(int i = 3;i < 26; ++i){
     59                 while(cnt[i]--)cout<<char('a' + i);
     60             }
     61             cout << "\n";
     62         }
     63     }
     64 }
     65 ```
     66 
     67 **Fun fact**
     68 
     69 Originally, the author and two testers' solutions are all wrong, but we didn't notice until the third tester submitted the real correct solution.
     70 
     71 [1617B - GCD Problem](/contest/1617/problem/B "Codeforces Round 761 (Div. 2)")
     72 
     73 **Hint**
     74 
     75 There must exist a solution for $c=1$ under the given constraints.
     76 
     77 **Solution**
     78 
     79 Key observation: there always exists a solution with $c = 1$ under the given constraints. We set $n \ge 10$ because there is no solution when $1 \le n \le 5$ or $n = 7$.
     80 
     81 Solution 1: Brute force from $a = 2, 3, 4, \dots$ and calculate the value of $b$ ($b = n - a - 1$), then check whether $gcd(a, b) = 1$. It works, because you will find a prime number $p \le 29$ such that $n-1$ does not divide $p$.
     82 
     83 Solution 2: Randomly choose $a$ and calculate $b$ ($b = n - a - 1$). Repeating that for enough times will eventually get you a pair of ($a, b$) such that $gcd(a, b) = 1$.
     84 
     85 Solution 3: Constructive solution.
     86 
     87 * When $n \equiv 0 \pmod 2$, output ($n-3, 2, 1$).
     88 * When $n \equiv 1 \pmod 4$, output ($\left \lfloor \frac{n}{2} \right \rfloor -1, \left \lfloor \frac{n}{2} \right \rfloor +1, 1$).
     89 * When $n \equiv 3 \pmod 4$, output ($\left \lfloor \frac{n}{2} \right \rfloor -2, \left \lfloor \frac{n}{2} \right \rfloor +2, 1$).
     90 
     91 **Implementation (Solution 1, Java, SecondThread)**
     92 
     93 ```
     94 import java.io.BufferedReader;
     95 import java.io.IOException;
     96 import java.io.InputStreamReader;
     97 import java.util.ArrayList;
     98 import java.util.Collections;
     99 import java.util.StringTokenizer;
    100 import java.util.Scanner;
    101 
    102 public class B {
    103 
    104 	public static void main(String[] args) {
    105 		Scanner fs = new Scanner(System.in);
    106 		int T=fs.nextInt();
    107 		for (int tt=0; tt<T; tt++) {
    108 			int n=fs.nextInt();
    109 			for (int target=2; true; target++) {
    110 				if (gcd(n-1-target, target)!=1)
    111 					continue;
    112 				System.out.println(n-1-target+" "+target+" "+1);
    113 				if (n-1-target<=1) throw null;
    114 				break;
    115 			}
    116 		}
    117 	}
    118 	
    119 	static int gcd(int a, int b) {
    120 		return b==0?a:gcd(b, a%b);
    121 	}
    122 
    123 	static void sort(int[] a) {
    124 		ArrayList<Integer> l=new ArrayList<>();
    125 		for (int i:a) l.add(i);
    126 		Collections.sort(l);
    127 		for (int i=0; i<a.length; i++) a[i]=l.get(i);
    128 	}
    129 	
    130 }
    131 ```
    132 
    133 **Implementation (Solution 2, C++, dbsic211)**
    134 
    135 ```
    136 #include <bits/stdc++.h>
    137 using namespace std;
    138 mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
    139 void solve(int tc) {
    140     int n; 
    141     cin >> n;
    142     while(1) {
    143         int k = uniform_int_distribution<int>(2, n-2)(rng);
    144         int l = n-k-1;
    145         if(k != l && k != 1 && l != 1 && gcd(k, l) == 1) {
    146             cout << k << ' ' << l << ' ' << 1 << endl;
    147             break;
    148         }
    149     }
    150 }
    151 
    152 int main() {
    153     int t;
    154     cin >> t;
    155     for(int i=1; i<=t; i++) {
    156         solve(i);
    157     }
    158 }
    159 ```
    160 
    161 **Implementation (Solution 3, C++, anthony123)**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 using namespace std;
    166 void solve(){
    167 	int n;
    168 	cin>>n;
    169 	if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";
    170 	else {
    171 		int cur=(n-1)/2;
    172 		if (cur%2==0) cout<<cur-1<<" "<<cur+1<<" "<<1<<endl;
    173 		else cout<<cur-2<<" "<<cur+2<<" "<<1<<endl;
    174 	}
    175 }
    176 signed main(){
    177 	int t;
    178 	cin>>t;
    179 	while (t--) solve();
    180 }
    181 ```
    182 
    183 [1617C - Paprika and Permutation](/contest/1617/problem/C "Codeforces Round 761 (Div. 2)")
    184 
    185 **Hint 1**
    186 
    187 For any two positive integers $x$, $y$ that satisfy $x \ge y$, what is the maximum value of $x \bmod y$?
    188 
    189 **Hint 2**
    190 
    191 Consider the following input: $n = 4$, $a = [3, 3, 10, 10]$. Sometimes, we don't need to do anything to some $a_i$. When do we have to make operations, and when do we not have to?
    192 
    193 **Solution**
    194 
    195 Key observation: $x \bmod y \lt \frac{x}{2}$ if $x \ge y$, and $x \bmod y = x$ if $x \lt y$.
    196 
    197 Notice that the bigger the $x$, the bigger the range of values that can be obtained after one $\bmod$ operation. So, intuitively, we want to assign smaller $a_i$ to smaller numbers in the resulting permutation.
    198 
    199 However, if $a_i$ satisfies $1 \le a_i \le n$, we can just leave it there and use it in the resulting permutation (if multiple $a_i$ satisfy $1 \le a_i \le n$ and have the same value, just choose one). Let's suppose in the optimal solution, we change $x$ to $y$ and change $z$ to $x$ for some $z \gt x \gt y$ ($x$, $y$, $z$ are values, not indices). Then changing $x$ to $x$ (i.e. doing nothing) and changing $z$ to $y$ uses $1$ less operation. And, if it is possible to change $z$ to $x$, then it must be possible to change $z$ to $y$. However, if it is not possible to change $z$ to $x$, it might still be possible to change $z$ to $y$.
    200 
    201 Therefore, the solution is as follows: Sort the array. For each element $i$ in the sorted array:
    202 
    203 * If $1 \le a_i \le n$ and it is the first occurrence of element with value $a_i$, leave it there.
    204 * Else, let the current least unassigned value in the resulting permutation be $m$, if $m \lt \frac{a_i}{2}$, we can assign the current element to value $m$ and add the number of operations by $1$. Else, output $-1$ directly.
    205 
    206 The solution works in $O(n \log n)$.
    207 
    208 **Implementation (C++, physics0523)**
    209 
    210 ```
    211 #include<bits/stdc++.h>
    212 using namespace std;
    213 int main(){
    214     ios::sync_with_stdio(false);
    215     cin.tie(nullptr);
    216     int t;
    217     cin >> t;
    218     while(t>0){
    219         t--;
    220         int n;
    221         cin >> n;
    222         set<int> st;
    223         for(int i=1;i<=n;i++){st.insert(i);}
    224         vector<int> rem;
    225         for(int i=0;i<n;i++){
    226             int v;
    227             cin >> v;
    228             if(st.find(v)!=st.end()){st.erase(v);}
    229             else{rem.push_back(v);}
    230         }
    231         sort(rem.begin(),rem.end());
    232         reverse(rem.begin(),rem.end());
    233         int pt=0;
    234         bool err=false;
    235         for(auto &nx : rem){
    236             auto it=st.end();
    237             it--;
    238             int ctg=(*it);
    239             if(ctg>(nx-1)/2){err=true;break;}
    240             st.erase(it);
    241         }
    242         if(err){cout << "-1\n";}
    243         else{cout << rem.size() << '\n';}
    244     }
    245     return 0;
    246 }
    247 ```
    248 
    249 [1617D1 - Too Many Impostors (easy version)](/contest/1617/problem/D1 "Codeforces Round 761 (Div. 2)")
    250 
    251 **Hint 1**
    252 
    253 The weird constraint, $\frac{n}{3} \lt k \lt \frac{2n}{3}$, is crucial.
    254 
    255 **Hint 2**
    256 
    257 If you know the index of one crewmate and one impostor, how to find the roles of other $n-2$ players in exactly $n-2$ queries?
    258 
    259 **Hint 3**
    260 
    261 Query players ($1, 2, 3$), ($2, 3, 4$), $\dots$, ($n-1, n, 1$), ($n, 1, 2$). After that, you can surely find out the index of one crewmate and one impostor. Try to find out how.
    262 
    263 **Solution**
    264 
    265 Key observation: if result of query ($a, b, c$) $\ne$ result of query ($b, c, d$), since $b$ and $c$ are common, players $a$ and $d$ have different roles. Additionally, if result of query ($a, b, c$) = $1$ then player $a$ is a crewmate (and player $d$ is an impostor), vice versa.
    266 
    267 The first step is to query players ($1, 2, 3$), ($2, 3, 4$), $\dots$, ($n-1, n, 1$), ($n, 1, 2$).
    268 
    269 If the results of any two adjacent queries (or queries ($1, 2, 3$) and ($n, 1, 2$)) are different, we instantly know the roles of the two players that are only included in one query — one is a crewmate, one is an impostor. Since the number of impostors $k$ and crewmates $n-k$ satisfy $k \gt \frac{n}{3}$ and $n - k \gt \frac{n}{3}$, there must be one pair of adjacent queries that are different.
    270 
    271 After we know one crewmate and one impostor (let's call them $a$, $d$), we can query these two players with each one of the rest of the players. If a query ($a, d, x$) ($1 \le x \le n$, $x \ne a$ and $x \ne d$) returns $0$, player $x$ is an impostor, else player $x$ is a crewmate.
    272 
    273 In total, $2n-2$ queries are used.
    274 
    275 **Implementation (C++, dbsic211)**
    276 
    277 ```
    278 #include <bits/stdc++.h>
    279 using namespace std;
    280 void solve() {
    281     int N; 
    282     cin >> N;
    283     int res[N];
    284     for(int i=0; i<N; i++) {
    285         cout << "? " << i + 1 << " " << (i+1) % N + 1 << " " << (i+2) % N + 1 << endl;
    286         cin >> res[i];
    287     }
    288     vector<int> imp;
    289     for(int i=0; i<N; i++) {
    290         if(res[i] != res[(i+1) % N]) {
    291             if(res[i] == 0) imp.push_back(i + 1);
    292             else imp.push_back((i+3) % N + 1);
    293             for(int j=0; j<N; j++) {
    294                 if(j != i && j != (i+3) % N) {
    295                     cout << "? " << i + 1 << " " << (i+3) % N + 1 << " " << j + 1 << endl;
    296                     int r;
    297                     cin >> r;
    298                     if(r == 0) imp.push_back(j + 1);
    299                 }
    300             }
    301             break;
    302         }
    303     }
    304     cout << "! " << imp.size();
    305     for(int x : imp) cout << " " << x;
    306     cout << endl;
    307 }
    308 int main() {
    309     int T;
    310     cin >> T;
    311     for(int i=1; i<=T; i++) {
    312         solve();
    313     }
    314 }
    315 ```
    316 
    317 [1617D2 - Too Many Impostors (hard version)](/contest/1617/problem/D2 "Codeforces Round 761 (Div. 2)")
    318 
    319 Thanks must be given to [arvindf232](/profile/arvindf232 "Grandmaster arvindf232") and [generic_placeholder_name](/profile/generic_placeholder_name "Master generic_placeholder_name") for the solution.
    320 
    321 **Hint 1**
    322 
    323 Aim to find an impostor and a crewmate's index in $\frac{n}{3} + c$ queries, with $c$ being a small constant.
    324 
    325 **Hint 2**
    326 
    327 Consider splitting the $n$ players into groups of $3$ (and query each group) in order to reach the goal in Hint 1. What is special about the results of the $\frac{n}{3}$ queries?
    328 
    329 **Solution (Step 1)**
    330 
    331 Firstly query ($1, 2, 3$), ($4, 5, 6$), $\dots$, ($n-2, n-1, n$). Due to the constraint $\frac{n}{3} \lt k \lt \frac{2n}{3}$, among the results of these $\frac{n}{3}$ queries, there must be at least one $0$ and one $1$. Now, let's call a tuple ($a, b, c$) that returns $0$ a $0$-majority tuple, and vice versa.
    332 
    333 From the easy version, notice that finding one crewmate and one impostor is very helpful in determining the roles of the remaining players. Let's make use of the above observation, and pick one adjacent $0$-majority tuple and $1$-majority tuple.
    334 
    335 Let's say we picked ($i, i+1, i+2$) and ($i+3, i+4, i+5$). Then, we query ($i+1, i+2, i+3$) and ($i+2, i+3, i+4$). Among the four queries ($i, i+1, i+2$), ($i+1, i+2, i+3$), ($i+2, i+3, i+4$), ($i+3, i+4, i+5$), there must be a pair of adjacent queries with different results. From the easy version, we can directly find the index of an impostor and a crewmate.
    336 
    337 In all the above cases, we end up knowing an impostor and a crewmate using $\frac{n}{3} + 2$ queries, including the first step.
    338 
    339 **Hint 3**
    340 
    341 You have the index of an impostor and a crewmate now, and around $\frac{2n}{3}$ queries left.
    342 
    343 Consider using at most $2$ queries to find out roles of each player in each group of $3$ from Step 1, which should add up to $\frac{2n}{3}$ queries.
    344 
    345 Make use of the information you know about each group (whether it is $0$-majority or $1$-majority).
    346 
    347 **Hint 4**
    348 
    349 Assume a tuple (group of $3$) is $0$-majority. There are $4$ possibilities of roles of the $3$ players in the tuple, which are:
    350 
    351 * impostor, impostor, impostor
    352 * crewmate, impostor, impostor (and its permutations)
    353 
    354 In each query, reduce half of the possibilities.
    355 
    356 **Solution (Step 2)**
    357 
    358 It remains to figure out how we can find the roles of the remaining players using $\frac{2n}{3}$ queries. For each tuple ($i, i+1, i+2$) queried in the first step, let's assume the tuple is $0$-majority (because the other case can be solved similarly). Then, there are only four possibilities:
    359 
    360 * All players $i$, $i+1$, $i+2$ are impostors.
    361 * Player $i$ is a crewmate, players $i+1$, $i+2$ are impostors.
    362 * Player $i+1$ is a crewmate, players $i$, $i+2$ are impostors.
    363 * Player $i+2$ is a crewmate, players $i$, $i+1$ are impostors.
    364 
    365 Earlier, we found the index of a crewmate and an impostor, let the index of the crewmate be $a$ and the impostor be $b$.
    366 
    367 If the tuple ($i, i+1, a$) is $1$-majority, either player $i$ or player $i+1$ is a crewmate. So, we reduced the number of possibilities to $2$. To check which player is the crewmate, query it with $a$ and $b$ like we did in the easy version.
    368 
    369 Else, either there are no crewmates or player $i+2$ is a crewmate. So, we reduced the number of possibilities to $2$. To check the role of player $i+2$, query it with $a$ and $b$ like we did in the easy version.
    370 
    371 In both cases, we use $2$ queries for each initial tuple ($i, i+1, i+2$). So, we used $n + 2$ queries in total, but we gave you a bit more, in case you used some more queries to find a crewmate and an impostor.
    372 
    373 There is one corner case we should handle: if the tuple ($i, i+1, i+2$) contains $a$ or $b$, we can just naively query for each unknown role in the tuple, since we won't use more than $2$ queries anyway.
    374 
    375 **Implementation (C++, dbsic211)**
    376 
    377 ```
    378 #include <bits/stdc++.h>
    379 using namespace std;
    380 int query(int a, int b, int c) {
    381     cout << "? " << a << ' ' << b << ' ' << c << endl;
    382     int r; cin >> r;
    383     return r;
    384 }
    385 void solve(int tc) {
    386     int n; cin >> n;
    387     int a[n+1], role[n+1];
    388     for(int i=1; i+2<=n; i+=3) a[i] = query(i, i+1, i+2);
    389     int imp, crew;
    390     for(int i=1; i<=n; i++) role[i] = -1;
    391     for(int i=1; i+5<=n; i+=3) {
    392         if(a[i] != a[i+3]) {
    393             a[i+1] = query(i+1, i+2, i+3), a[i+2] = query(i+2, i+3, i+4);
    394             for(int j=i; j<i+3; j++) {
    395                 if(a[j] != a[j+1]) {
    396                     if(a[j] == 0) {
    397                         imp = j, crew = j+3;
    398                         role[j] = 0, role[j+3] = 1;
    399                     }
    400                     else {
    401                         imp = j+3, crew = j;
    402                         role[j+3] = 0, role[j] = 1;
    403                     }
    404                 }
    405             }
    406             break;
    407         }
    408     }
    409     for(int i=1; i+2<=n; i+=3) {
    410         if(i == imp || i+1 == imp || i+2 == imp || i == crew || i+1 == crew || i+2 == crew) {
    411             for(int j=i; j<i+3; j++) {
    412                 if(role[j] == -1) {
    413                     role[j] = query(imp, crew, j);
    414                 }
    415             }
    416         }
    417         else if(a[i] == 0) {
    418             if(query(i, i+1, crew) == 1) {
    419                 if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
    420                 else role[i] = 1, role[i+1] = 0;
    421                 role[i+2] = 0; 
    422             }
    423             else {
    424                 role[i] = role[i+1] = 0;
    425                 role[i+2] = query(i+2, imp, crew);
    426             }
    427         }
    428         else {
    429             if(query(i, i+1, imp) == 0) {
    430                 if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
    431                 else role[i] = 1, role[i+1] = 0;
    432                 role[i+2] = 1; 
    433             }
    434             else {
    435                 role[i] = role[i+1] = 1;
    436                 role[i+2] = query(i+2, imp, crew);
    437             }
    438         }
    439     }
    440     cout << "! ";
    441     queue<int> q;
    442     for(int i=1; i<=n; i++) if(role[i] == 0) q.push(i);
    443     cout << q.size();
    444     while(q.size()) {
    445         cout << " " << q.front();
    446         q.pop();
    447     }
    448     cout << endl;
    449 }
    450 int main() {
    451     int T; cin >> T;
    452     for(int i=1; i<=T; i++) solve(i);
    453 }
    454 ```
    455 
    456 [1617E - Christmas Chocolates](/contest/1617/problem/E "Codeforces Round 761 (Div. 2)")
    457 
    458 **Hint 1**
    459 
    460 Translate the problem into a graph problem. What feature of the graph is it asking about?
    461 
    462 **Hint 2**
    463 
    464 Draw out the graph, for $a_i \le 10$. What special property does the graph have?
    465 
    466 **Hint 3**
    467 
    468 Any specific algorithm to solve the problem (in Hint 1)?
    469 
    470 **Solution (Step 1)**
    471 
    472 In graph terms, the problem is as follows: in a graph with infinite nodes, two nodes $x$ and $y$ are connected if $x + y = 2^k$ for some $k \ge 0$. Among $n$ special nodes, find the pair of nodes ($i, j$) with maximum shortest distance.
    473 
    474 Here comes the key observation: For any $i \ge 1$, there exists only one $j$ ($0 \le j \lt i$) such that $i + j = 2^k$ for some $k \ge 0$.
    475 
    476 The proof is as follows: let's say that $0 \le j_1, j_2 \lt i$, $j_1 \ge j_2$, $i + j_1 = 2^{k_1}$, $i + j_2 = 2^{k_2}$. Then, $j_1 - j_2 = 2^{k_2} \cdot (2^{k_1-k_2} - 1)$. So, $j_1 \equiv j_2 \pmod {2^{k_2}}$. Since $i \le 2^{k_2}$, $j_1 = j_2$.
    477 
    478 Then, we realize we can build a graph as follows: add an edge between $x$ and $y$ ($x, y \ge 0$) if $x + y = 2^k$ for some $k \ge 0$. Because of the first key observation, the graph must be **a tree**. We can root the tree at node $0$.
    479 
    480 Our problem is equivalent to finding the pair of nodes which have maximum distance in a tree, which can be solved using the diameter of tree algorithm.
    481 
    482 **Hint 4**
    483 
    484 We can't build the entire tree as it has $10^9 + 1$ nodes. Try to notice something about the depth of the tree, then think of how this could help us solve the problem (by building the tree, or otherwise).
    485 
    486 **Solution (Step 2)**
    487 
    488 Since $0 \le a_i \le 10^9$, it is impossible to build the entire tree. A final observation is that: Consider any node $v$ with degree $\ge 2$ in the tree, then $v \gt p_v$ and $p_v \gt p_{p_v}$, therefore $v + p_v \gt p_v + p_{p_v}$ ($p_x$ denotes the parent of node $x$ in the tree).
    489 
    490 Hence the depth of the tree is $\lceil \log(max(a_i)) \rceil = 30$, since there are only $\lceil \log(max(a_i)) \rceil$ possible $k$ ($0 \le k \lt 30$) for the sum of two nodes connected by an edge.
    491 
    492 So, there are two ways to do it: the first way is to build parts of the tree: only the $n$ given nodes and the ancestors of the $n$ nodes. There will be at most $O(n \log max(a_i))$ nodes, which should fit into the memory limit. The second way is to not build the tree at all, and calculate the LCA (Lowest Common Ancestor) of two nodes to find their distance. Since the depth of the tree is $30$, LCA of two nodes can be computed by simply checking every ancestor of both nodes.
    493 
    494 In both ways, the time complexity is $O(n \log max(a_i))$.
    495 
    496 **Implementation (C++, physics0523)**
    497 
    498 ```
    499 #include<bits/stdc++.h>
    500 using namespace std;
    501 
    502 int f(int x){
    503     for(int i=0;;i++){
    504         if((1<<i)>=x){
    505             return (1<<i)-x;
    506         }
    507     }
    508 }
    509 
    510 using pi=pair<int,int>;
    511 int main(){
    512     ios::sync_with_stdio(false);
    513     cin.tie(nullptr);
    514     int n;
    515     cin >> n;
    516     map<int,pair<pi,pi>> mp;
    517     priority_queue<int> pq;
    518     for(int i=0;i<n;i++){
    519         int v;
    520         cin >> v;
    521         pq.push(v);
    522         mp[v].first=make_pair(0,i+1);
    523     }
    524     while(!pq.empty()){
    525         int od=pq.top();pq.pop();
    526         if((!pq.empty()) && od==pq.top()){continue;}
    527         if(od!=1){
    528             int nx=f(od);
    529             pq.push(nx);
    530             pi send=mp[od].first;
    531             send.first++;
    532             if(mp[nx].first<send){
    533                 mp[nx].second=mp[nx].first;
    534                 mp[nx].first=send;
    535             }
    536             else if(mp[nx].second<send){mp[nx].second=send;}
    537         }
    538     }
    539     int ra=0,rb=0,rc=-1;
    540     for(auto &nx : mp){
    541         pair<pi,pi> tg=nx.second;
    542         if(tg.first.second==0 || tg.second.second==0){continue;}
    543         if(rc<tg.first.first+tg.second.first){
    544             rc=tg.first.first+tg.second.first;
    545             ra=tg.first.second;
    546             rb=tg.second.second;
    547         }
    548     }
    549     cout << ra << ' ' << rb << ' ' << rc << '\n';
    550     return 0;
    551 }
    552 ```