Submission #532902

#TimeUsernameProblemLanguageResultExecution timeMemory
532902hhhhauraCheerleaders (info1cup20_cheerleaders)C++14
72 / 100
1887 ms1228 KiB
#define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i--) #define ceil(a, b) ((a + b - 1) / (b)) #define all(x) x.begin(), x.end() #define lld long double #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) using namespace std; #define INF 1000000000 #define MOD 1000000007 #define eps (1e-9) #ifdef wiwihorz #define print(a...) cerr<<"Line "<<__LINE__<<":",kout("[" + string(#a) + "] = ", a) void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;} void kout() { cerr << endl; } template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif #define x first #define y second struct BIT { int n; vector<int> v; void init_(int _n) { n = _n; v.assign(n + 1, 0); } int lowbit(int x) { return x & (-x); } void modify(int x, int val) { for(int i = x; i <= n; i += lowbit(i)) { v[i] += val; } } int query(int x) { int ans = 0; for(int i = x; i > 0; i -= lowbit(i)) { ans += v[i]; } return ans; } }; namespace solver { int n, tot; BIT bit; vector<int> a, b; void init_(int _n) { n = _n, tot = 1 << n; a.assign(tot, 0); b.assign(tot, 0); } int cal() { bit.init_(tot); int ans = 0; rrep(i, 0, tot - 1) { int val = a[b[i]] + 1; ans += bit.query(val - 1); bit.modify(val, 1); } return ans; } string get_ans(pii opt) { string s = "2"; rep(i, 0, n - 1) { if((opt.x >> i) & 1) s += "1"; s += "2"; } rep(i, 1, n - 1 - opt.y) s += "2"; return s; } void solve1() { rep(i, 0, tot - 1) b[a[i]] = i; pii opt = {0, 0}; rep(i, 0, n - 1) if((b[0] >> i) & 1) { opt.x |= (1 << i); } int ii = 0; while((b[ii] & 1) == (b[0] & 1)) ii++; opt.y = 31 - __builtin_clz(ii); cout << 0 << "\n"; cout << get_ans(opt) << "\n"; } void solve() { int ans = INF; pii opt; if(n == 0) { cout << 0 <<"\n"; return; } rep(i, 0, tot - 1) rep(j, 0, n - 1) { rep(x, 0, tot - 1) b[x] = 0; rep(x, 0, tot - 1) rep(y, 0, n - 1) { int to = (j + y >= n ? j + y - n : j + y); b[x] |= ((((x >> to) & 1) ^ ((i >> y) & 1)) << y); } int val = cal(); if(val < ans) ans = val, opt = {i, j}; } cout << ans << "\n"; cout << get_ans(opt) << "\n"; } }; using namespace solver; signed main() { ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; init_(n); rep(i, 0, (1 << n) - 1) cin >> a[i]; if(n <= 11) solve(); else solve1(); return 0; }

Compilation message (stderr)

cheerleaders.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
cheerleaders.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |             ^~~~
cheerleaders.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |                     ^~~~
#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...