CSES - Datatähti Open 2021 - Results
Submission details
Task:Sorting
Sender:lookcook
Submission time:2021-01-30 17:59:29 +0200
Language:C++ (C++17)
Status:READY
Result:36
Feedback
groupverdictscore
#1ACCEPTED36
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#20.99 s2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.13 s1, 2details

Compiler report

input/code.cpp: In function 'void rec(std::vector<long long int>)':
input/code.cpp:11:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size()-1; i++) {
                     ~~^~~~~~~~~~~~
input/code.cpp:12:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i+2; j < v.size()-1; j++) {
                           ~~^~~~~~~~~~~~
input/code.cpp:14:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < v.size(); k++) to.push_back(v[k]);
                             ~~^~~~~~~~~~

Code

#include <bits/stdc++.h>

#define int long long

using namespace std;

set<vector<int>> vis;
void rec(vector<int> v) {
    if (vis.count(v) != 0) return;
    vis.insert(v);
    for (int i = 0; i < v.size()-1; i++) {
        for (int j = i+2; j < v.size()-1; j++) {
            vector<int> to;
            for (int k = 0; k < v.size(); k++) to.push_back(v[k]);
            swap(to[i],to[i+1]);
            swap(to[j],to[j+1]);
            rec(to);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        bool sorted = true;
        vector<int> a;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            a.push_back(x);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[i]<a[j]) {
                    sorted = false;
                }
            }
        }
        if (n <= 3) {
            if (sorted) cout << "YES\n";
            else cout << "NO\n";
            continue;
        }
        if (n == 4) {
            if (sorted || (a[0] == 3 && a[1] == 4 && a[2] == 1 && a[3] == 2)) cout << "YES\n";
            else cout << "NO\n";
            continue;
        }
        vector<int> v;
        for (int i = 1; i <= n; i++) v.push_back(i);
        rec(v);
        /*for (vector<int> x : vis) {
            for (int i : x) cout << i << ' ';
            cout << '\n';
            int inv = 0;
            int e = 0;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (x[i]<x[j]) inv++;
                }
                if (x[i]<x[i-1]) e++;
            }
            cout << "Inv = " << inv << '\n';
            cout << "E = " << e << '\n';
        }*/
        if (vis.count(a) == 0) cout << "NO\n";
        else cout << "YES\n";
    }
}
/*
1
5
1 2 3 4 5

*/

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
153
1
1
2
1 2
...

correct output
YES
YES
NO
NO
NO
...

user output
YES
YES
NO
NO
NO
...
Truncated

Test 2

Group: 2

Verdict:

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

correct output
YES
NO
YES
NO
YES
...

user output
(empty)

Test 3

Group: 1, 2

Verdict: ACCEPTED

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

correct output
YES
NO
NO
NO
YES
...

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
...

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
YES
NO
YES
...
Truncated