— Dark mode

Datatähti Open 2021

Sorting

  • Start: N/A
  • End: N/A
CSES - Datatähti Open 2021 - Results
Submission details
Task:Sorting
Sender:smjleo
Submission time:2021-02-01 15:43:16 +0200
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED36
#2ACCEPTED64
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.01 s1, 2details

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1000000007;
const int mod2 = 998244353;

// change this
const int N = 105;

int t, n, arr[N];

signed main() {
    io;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i<n; i++) cin >> arr[i];
        bool sorted = true;
        for (int i=1; i<n; i++) {
            if (arr[i-1] > arr[i]) {
                sorted = false;
                break;
            }
        }
        if (sorted) {
            cout << "YES" << nl;
            continue;
        }
        // not sorted
        if (n <= 3) {
            cout << "NO" << nl;
            continue;
        }
        if (n == 4) {
            if (arr[0] == 3 && arr[1] == 4 && arr[2] == 1 && arr[3] == 2) {
                cout << "YES" << nl;
            } else {
                cout << "NO" << nl;
            }
            continue;
        }
        int inv = 0;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (arr[i] > arr[j]) inv++;
            }
        }
        cout << (inv%2 ? "NO" : "YES") << nl;
    }
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
153
1
1
2
1 2
...
view save

correct output
YES
YES
NO
NO
NO
...
view save

user output
YES
YES
NO
NO
NO
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
59
35 29 32 50 11 15 9 21 19 45 2...
view save

correct output
YES
NO
YES
NO
YES
...
view save

user output
YES
NO
YES
NO
YES
...
Truncated

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
720
6
1 6 4 5 2 3
6
6 3 2 1 5 4
...
view save

correct output
YES
NO
NO
NO
YES
...
view save

user output
YES
NO
NO
NO
YES
...
Truncated

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
1000
8
7 4 2 8 6 3 5 1
8
3 8 2 7 5 4 6 1
...
view save

correct output
NO
NO
YES
NO
YES
...
view save

user output
NO
NO
YES
NO
YES
...
Truncated

Tasks

A Greater Integers-B Split in Three-C Sorting-D Distances-E Programmers-F Polygonal Chain-

Submissions (smjleo)

2021-02-01 15:43:16 100