Task: | Sorting |
Sender: | ScarletS |
Submission time: | 2021-01-30 20:58:36 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2 | details |
#3 | ACCEPTED | 0.33 s | 1, 2 | details |
#4 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
Code
#include <bits/stdc++.h>#define ll long long#define sz(x) (int)(x).size()using namespace std;int n;set<vector<int>> s;void dfs(vector<int> v){if (s.find(v)!=s.end())return;s.insert(v);for (int i=0;i+1<n;++i)for (int j=i+2;j+1<n;++j){swap(v[i],v[j]);swap(v[i+1],v[j+1]);dfs(v);swap(v[i],v[j]);swap(v[i+1],v[j+1]);}}void solve(){cin>>n;vector<int> v(n), w(n);for (int i=0;i<n;++i)cin>>v[i];iota(w.begin(), w.end(), 1);s.clear();dfs(v);if (s.find(w)==s.end())cout<<"NO\n";elsecout<<"YES\n";}int main(){ios_base::sync_with_stdio(0); cin.tie(0);int tc;cin>>tc;while (tc--)solve();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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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 |
---|
(empty) |