1674D - A-B-C Sort - CodeForces Solution

constructive algorithms implementation sortings *1200

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    
    n=int(input())
    l=list(map(int,input().split()))


    b=[0]*n  

    ans=[]

    if n&1:
        cnt=n  
        b[n//2]=l[0]
        i=(n//2)-1
        j=(n//2)+1

        k=1
        

        while cnt>0 and k<n:

            b[i]=l[k]
            b[j]=l[k+1]
            i-=1
            j+=1

            k+=2
            cnt-=1


        cnt=n 
        i=(n//2)-1
        j=(n//2)+1

        while cnt>0:

            if cnt&1:
                ans.append(b[cnt//2])

                cnt-=1

            else:
                ans.append(min(b[i],b[j]))
                ans.append(max(b[i],b[j]))
                i-=1
                j+=1
                cnt-=2

            

    else:
        cnt=n 
        i=n//2
        j=i-1
        k=0
        while cnt>0 and k<n:
            b[i]=l[k]
            b[j]=l[k+1]
            i+=1
            j-=1
            k+=2
            cnt-=1

            
        cnt=n 
        i=(n//2)
        j=(n//2)-1

        while cnt>0:
            ans.append(min(b[i],b[j]))
            ans.append(max(b[i],b[j]))

            i+=1
            j-=1
            cnt-=2


    for i in range(1,len(ans)):
        if ans[i]<ans[i-1]:
            print("NO")
            break

    else:
        print("YES")

C++ Code: 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int TC;
    cin >> TC;
    while (TC--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> res;
        if (n % 2 == 1) {
            res.push_back(a[0]);
            for (int i = 1; i < n; i += 2) {
                if (a[i] < a[i + 1]) {
                    res.push_back(a[i]);
                    res.push_back(a[i + 1]);
                } else {
                    res.push_back(a[i + 1]);
                    res.push_back(a[i]);
                }
            }
        } else {
            for (int i = 0; i < n; i += 2) {
                if (a[i] < a[i + 1]) {
                    res.push_back(a[i]);
                    res.push_back(a[i + 1]);
                } else {
                    res.push_back(a[i + 1]);
                    res.push_back(a[i]);
                }
            }

        }

        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (res[i - 1] > res[i]) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

660A - Co-prime Array
1692F - 3SUM
1470A - Strange Birthday Party
190D - Non-Secret Cypher
1721B - Deadly Laser
1721C - Min-Max Array Transformation
1721A - Image
1180C - Valeriy and Deque
557A - Ilya and Diplomas
1037D - Valid BFS
1144F - Graph Without Long Directed Paths
1228A - Distinct Digits
355B - Vasya and Public Transport
1230A - Dawid and Bags of Candies
1530A - Binary Decimal
1472D - Even-Odd Game
441C - Valera and Tubes
1328E - Tree Queries
265A - Colorful Stones (Simplified Edition)
296A - Yaroslav and Permutations
967B - Watering System
152A - Marks
1398A - Bad Triangle
137A - Postcards and photos
1674D - A-B-C Sort
334A - Candy Bags
855A - Tom Riddle's Diary
1417A - Copy-paste
1038A - Equality
1061A - Coins