제출 #418325

#제출 시각아이디문제언어결과실행 시간메모리
418325dolphingarlicCheerleaders (info1cup20_cheerleaders)C++14
31 / 100
2075 ms1356 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; int n, h[1 << 17], at[1 << 17]; ll bit[(1 << 17) + 1]; void ins(int pos) { for (; pos <= (1 << n); pos += pos & -pos) bit[pos]++; } ll query(int pos) { ll ans = 0; for (; pos; pos -= pos & -pos) ans += bit[pos]; return ans; } ll check(int mask, int shift) { memset(bit, 0, sizeof bit); ll ans = 0; for (int i = (1 << n) - 1; ~i; i--) { int masked = at[i] ^ mask; for (int j = 0; j < shift; j++) masked = (masked >> 1) + ((masked & 1) << n - 1); ans += query(masked + 1); ins(masked + 1); } return ans; } 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; } if (n <= 11) { ll mn = LLONG_MAX; string best_seq; for (int mask = 0; mask < (1 << n); mask++) { for (int shift = 0; shift < n; shift++) { int pot = check(mask, shift); if (pot < mn) { string seq; for (int i = 0; i < n; i++) { seq += "2"; if (mask & (1 << i)) seq += "1"; } for (int i = 0; i < shift; i++) seq += "2"; mn = pot; best_seq = seq; } } } cout << mn << '\n' << best_seq; } else { cout << 0 << '\n'; for (int i = 0; i < n; i++) { cout << 2; if (at[0] & (1 << i)) cout << 1; } for (int j = 0; j < __builtin_ctz(at[0] ^ at[1]); j++) cout << 2; } return 0; }

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

cheerleaders.cpp: In function 'll check(int, int)':
cheerleaders.cpp:24:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |             masked = (masked >> 1) + ((masked & 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...