Codeforces Round #826 (Div. 3) 1741D - Masha and a Beautiful Tree Solution

 Problem Link:  https://codeforces.com/problemset/problem/1741/D

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. vector<int> a;
10. int ans = 0;
11. void func(int l1, int r1, int l2, int r2) {
12. int mxl = 0;
13. int mnr = INT_MAX;
14. for (int i = l1; i <= r1; i++) {
15. mxl = max(mxl, a[i]);
16. }
17. for (int i = l2; i <= r2; i++) {
18. mnr = min(mnr, a[i]);
19. }
20. if (mxl > mnr) {
21. int R = l2;
22. for (int i = l1; i <= r1; i++) {
23. swap(a[i], a[R]);
24. R++;
25. }
26. ans++;
27. }
28. if (l1 == r1) return;
29. int mid1 = (l1 + r1) / 2;
30. int mid2 = (l2 + r2) / 2;
31. func(l1, mid1, mid1 + 1, r1);
32. func(l2, mid2, mid2 + 1, r2);
33. }
34. int main() {
35. ios_base::sync_with_stdio(0);
36. cin.tie(0);
37. int t;
38. cin >> t;
39. while (t--) {
40. int n;
41. cin >> n;
42. a.resize(n + 1);
43. for (int i = 1; i <= n; i++) cin >> a[i];
44. if (is_sorted(a.begin() + 1, a.begin() + n + 1)) {
45. cout << 0 << endl;
46. continue;
47. }
48. ans = 0;
49. int mid = (n + 1) / 2;
50. func(1, mid, mid + 1, n);
51. if (is_sorted(a.begin() + 1, a.begin() + n + 1)) {
52. cout << ans << endl;
53. } else
54. cout << "-1" << endl;
55. }
56. }