제출 #388611

#제출 시각아이디문제언어결과실행 시간메모리
388611warner1129Cheerleaders (info1cup20_cheerleaders)C++17
51 / 100
589 ms3588 KiB
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; const int maxn = 17; pair<long long, long long> cnt[maxn]; long long ans = 0x3f3f3f3f3f3f3f; int opt = 0, h = 0; int n; void dfs(int d, vector<int> vec) { long long c0, c1, t0, t1; vector<int> L, R; c0 = c1 = t0 = t1 = 0; for (int v : vec) { if ((v>>d) & 1) c1++, t1 += c0, R.emplace_back(v); else c0++, t0 += c1, L.emplace_back(v); } cnt[d].ff += t0, cnt[d].ss += t1; if (d--) dfs(d, L), dfs(d, R); } void solve() { cin >> n; ans = (1<<n) * ((1<<n)-1) / 2; vector<int> vec(1<<n); for (int i = 0, x; i < 1<<n; i++) cin >> x, vec[x] = i; long long cntmp = 0, optmp = 0; for (int i = 0; i < n; i++) { dfs(n-1, vec); cntmp = optmp = 0; for (int j = 0; j < n; j++) { if (cnt[j].ff > cnt[j].ss) cntmp += cnt[j].ss, optmp |= (1<<((j+i)%n)); else cntmp += cnt[j].ff; cnt[j] = {0, 0}; } if (cntmp < ans) ans = cntmp, opt = optmp, h = i; for (int j = 0; j < 1<<n; j++) vec[j] = (vec[j]>>1) | ((vec[j]&1)<<(n-1)); } string str; for (int i = 0; i < n; i++) { str.push_back('2'); if ((opt>>i)&1) str.push_back('1'); } while (h--) str.push_back('2'); cout << ans << '\n' << str << '\n'; } signed main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...