Codeforces Round #839 (Div. 3) 1772D - Absolute Sorting Solution

 

Problem Link: https://codeforces.com/contest/1772/problem/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. #define ll long long int
10. int main() {
11. ios_base::sync_with_stdio(0);
12. cin.tie(0);
13. int t;
14. cin >> t;
15. while (t--) {
16. int n;
17. cin >> n;
18. std::vector<int> v(n);
19. for (int i = 0; i < n; i++) cin >> v[i];
20. int low = 0, high = 1e9;
21. for (int i = 0; i < n - 1; i++) {
22. if (v[i] == v[i + 1])
23. continue;
24. else if (v[i] < v[i + 1]) {
25. int x = (v[i] + v[i + 1]) / 2;
26. high = min(high, x);
27. } else {
28. int x = (v[i] + v[i + 1] + 1) / 2;
29. low = max(low, x);
30. }
31. }
32. if (low <= high)
33. cout << high << endl;
34. else
35. cout << "-1" << endl;
36. }
37. }