Task: | Sorting |
Sender: | lookcook |
Submission time: | 2021-01-30 17:59:29 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 36 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 36 |
#2 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | RUNTIME ERROR | 0.99 s | 2 | details |
#3 | ACCEPTED | 0.01 s | 1, 2 | details |
#4 | ACCEPTED | 0.13 s | 1, 2 | details |
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: RUNTIME ERROR
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 |