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

Code

#include <bits/stdc++.h>
using namespace std;
set<int> vis;
int geh(const vector<int>& v) {
int num = 0;
const int n = (int)v.size();
for (int i = 0; i < n; ++i) {
num *= 10;
num += v[i];
}
return num;
}
int sz;
void go(vector<int>& arr) {
int h = geh(arr);
if (vis.find(h) != vis.end()) return;
vis.insert(h);
for (int i = 0; i < sz; ++i) {
for (int j = 2+i; 1+j < sz; ++j) {
swap(arr[i], arr[j]);
swap(arr[1+i], arr[1+j]);
go(arr);
swap(arr[i], arr[j]);
swap(arr[1+i], arr[1+j]);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
vector<int> arr;
for (int i = 1; i <= 8; ++i) {
arr.push_back(i);
sz = (int)arr.size();
go(arr);
}
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int h = geh(a);
cout << (n > 8 || vis.find(h) != vis.end() ? "YES" : "NO") << '\n';
}
return 0;
}

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

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