제출 #418403

#제출 시각아이디문제언어결과실행 시간메모리
418403dolphingarlicCheerleaders (info1cup20_cheerleaders)C++14
72 / 100
2043 ms2380 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; int n, h[1 << 17], at[1 << 17]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 0; i < (1 << n); i++) { cin >> h[i]; at[h[i]] = i; } ll mn = LLONG_MAX; string best_seq; for (int shift = 0; shift < max(1, n); shift++) { int mask = 0; ll inv_tot = 0; for (int i = n - 1; ~i; i--) { ll inv_0 = 0, inv_1 = 0; for (int j = 0; j < (1 << n); j += 1 << i + 1) { vector<int> left, right; for (int k = j; k < j + (1 << i); k++) left.push_back(h[k]); for (int k = j + (1 << i); k < j + (1 << i + 1); k++) right.push_back(h[k]); sort(left.begin(), left.end()); sort(right.begin(), right.end()); for (int j : left) inv_0 += lower_bound(right.begin(), right.end(), j) - right.begin(); for (int j : right) inv_1 += lower_bound(left.begin(), left.end(), j) - left.begin(); } if (inv_0 > inv_1) mask += 1 << i; inv_tot += min(inv_0, inv_1); if (inv_tot >= mn) break; } if (inv_tot < mn) { string seq; for (int i = 0; i < shift; i++) seq += "2"; for (int i = 0; i < n; i++) { seq += "2"; if (mask & (1 << i)) seq += "1"; } mn = inv_tot; best_seq = seq; } for (int i = 0; i < (1 << n); i++) { at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1); h[at[i]] = i; } } cout << mn << '\n' << best_seq; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:22:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 |             for (int j = 0; j < (1 << n); j += 1 << i + 1) {
      |                                                     ~~^~~
cheerleaders.cpp:25:60: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |                 for (int k = j + (1 << i); k < j + (1 << i + 1); k++) right.push_back(h[k]);
      |                                                          ~~^~~
cheerleaders.cpp:51:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |             at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1);
      |                                                    ~~^~~
#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...