제출 #387665

#제출 시각아이디문제언어결과실행 시간메모리
387665casperwangCheerleaders (info1cup20_cheerleaders)C++14
51 / 100
2085 ms8948 KiB
#include <bits/stdc++.h> #define pb emplace_back #define All(x) x.begin(), x.end() #define pii pair<int,int> #define ff first #define ss second using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } const int MAXN = 17; int N; int ans; pii op; string ops; vector <int> a, c; int val[MAXN+1]; inline int lb(int a) { return a &- a; } void init() { a.resize(1<<N); c.resize(1<<N); } class Bit { private: int arr[1<<MAXN+1]; public: void mdy(int a, int k) { for (int i = a; i <= (1<<N); i+=lb(i)) arr[i] += k; } int qry(int a) { int s = 0; for (int i = a; i; i-=lb(i)) s += arr[i]; return s; } } bit; int cnt_inv(vector <int> c) { int s = 0; vector <int> del; for (int i = 0; i < (1<<N); i++) { s += i - bit.qry(c[i]); bit.mdy(c[i]+1, 1); del.pb(i+1); } for (int i : del) bit.mdy(i, -1); return s; } void build() { int s = 0; for (int i = 0; i < N; i++) { vector <vector<int>> arr(1<<(N-i)); val[i] = 0; for (int j = 0; j < (1<<N); j++) { arr[c[j]/(1<<i)].pb(j); } for (int j = 0; j < (1<<(N-i)); j+=2) { vector <int> del; for (int k : arr[j]) { bit.mdy(k+1, 1); del.pb(k+1); } for (int k : arr[j+1]) { val[i] += (1<<i) - bit.qry(k); } for (int k : del) bit.mdy(k, -1); } s += val[i]; } } void test(string str, vector <int> c) { for (int i = 0; i < str.size(); i++) { if (str[i] == '2') { for (int j = 0; j < (1<<N); j++) { c[j] = (1<<(N-1)) * (c[j] & 1) + c[j] / 2; } } else if (str[i] == '1') { for (int j = 0; j < (1<<N); j++) { c[j] ^= (1<<(N-1)); } } } pary(All(c)); } string solve(pii op) { string str; for (int i = 0; i < op.ff; i++) str += '2'; for (int i = 0; i < N; i++) { str += '2'; if ((1<<i) & op.ss) { str += '1'; } } return str; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N; init(); for (int i = 0; i < (1<<N); i++) cin >> a[i], c[a[i]] = i; ans = cnt_inv(c); for (int j = 0; j < N; j++) { build(); int sum = cnt_inv(c); int x = 0; vector <int> tmp = c; for (int i = 1; i < (1<<N); i++) { int p = lb(i); for (int k = 0; k < (1<<N); k++) { c[k] ^= p; } x ^= p; int O = (1<<N) * p / 2; sum += O - 2 * val[__lg(p)]; val[__lg(p)] = O - val[__lg(p)]; if (sum < ans) { ans = sum, op = pii(j, x); } } c = tmp; for (int i = 0; i < (1<<N); i++) { c[i] = (1<<(N-1)) * (c[i] & 1) + c[i] / 2; } } cout << ans << '\n'; cout << solve(op) << '\n'; return 0; }

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

cheerleaders.cpp:32:18: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |   int arr[1<<MAXN+1];
      |              ~~~~^~
cheerleaders.cpp: In function 'void test(std::string, std::vector<int>)':
cheerleaders.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
#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...