# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
753694 | 2023-06-05T17:36:10 Z | Stickfish | Cheerleaders (info1cup20_cheerleaders) | C++17 | 2000 ms | 3616 KB |
#include <iostream> #include <vector> using ll = long long; using namespace std; ll get_inversion(vector<int>& p) { int n = p.size(); ll ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { ans += p[i] > p[j]; } return ans; } vector<int> combine_permutations(vector<int> a, vector<int> b) { int n = a.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) { ans[i] = b[a[i]]; } return ans; } vector<int> reverse_permutation(vector<int> a) { int n = a.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) ans[a[i]] = i; return ans; } pair<ll, string> get_ans(vector<int> p) { int n = p.size(); vector<int> aaa = p; ll ans = get_inversion(aaa); int ansx = 0; //for (int bt = n / 2; bt > 0; bt /= 2) { //int nx = ansx + bt; for (int nx = 0; nx < n; ++nx) { vector<int> op(n); for (int i = 0; i < n; ++i) op[i] = i ^ nx; vector<int> np = combine_permutations(op, p); ll nans = get_inversion(np); if (nans < ans) { ans = nans; ansx = nx; } } //cout << ans << ' ' << ansx << endl; return {ans, "12111"}; } signed main() { int N; cin >> N; int m = (1 << N); vector<int> p(m); for (int i = 0; i < m; ++i) cin >> p[i]; vector<int> op1(m); vector<int> op2(m); for (int i = 0; i < m; ++i) { op1[i] = i ^ (m / 2); op2[i] = (i >> 1) + ((i & 1) << (N - 1)); } ll ans = 1ll * m * m;; string ansa; for (int t = 0; t < N; ++t) { auto [nans, nansa] = get_ans(p); if (nans < ans) { ans = nans; ansa = nansa; } p = combine_permutations(op2, p); } cout << ans << '\n'; cout << ansa << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | Wrong number of inversions |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Correct number of inversions, wrong sequence of operations |
2 | Correct | 7 ms | 300 KB | Correct number of inversions, wrong sequence of operations |
3 | Correct | 7 ms | 304 KB | Correct number of inversions, wrong sequence of operations |
4 | Correct | 6 ms | 300 KB | Correct number of inversions, wrong sequence of operations |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2053 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2055 ms | 1760 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2043 ms | 3616 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |