# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
369363 | 2021-02-21T12:26:30 Z | doowey | Cheerleaders (info1cup20_cheerleaders) | C++14 | 1854 ms | 19068 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int main(){ fastIO; int n; cin >> n; if(n == 0){ cout << 0 << "\n"; return 0; } int m = (1 << n); vector<int> H(m); for(int i = 0 ; i < m ; i ++ ){ cin >> H[i]; } ll best = (ll)1e18; vector<int> soln; ll cur; ll inv; ll w0, w1; int pp; int z; vector<int> cha; for(int shf = 0; shf < n; shf ++ ){ vector<int> ord; vector<bool> swi(n); for(int j = shf; j < n - 1; j ++) { ord.push_back(j); } ord.push_back(n-1); for(int j = 0 ; j < shf; j ++ ){ ord.push_back(j); } vector<vector<pii>> pv; vector<vector<pii>> nw; pv.push_back({}); cur = 0; for(int i = 0 ;i < m ; i ++ ){ pv.back().push_back(mp(H[i],i)); } sort(pv.back().begin(), pv.back().end()); cha.clear(); for(int i = n - 1; i >= 0; i -- ){ nw.clear(); w0 = w1 = 0; for(auto x : pv){ vector<pii> f[2]; for(auto y : x){ if((y.se & (1 << ord[i]))){ f[1].push_back(y); } else{ f[0].push_back(y); } } pp = 0; inv = 0; z = f[0].size(); for(auto x : f[0]){ while(pp < f[1].size() && f[1][pp].fi < x.fi){ pp ++ ; } inv += pp; } w0 += inv; w1 += (z * 1ll * z) - inv; nw.push_back(f[0]); nw.push_back(f[1]); } pv = nw; if(w0 < w1){ cur += w0; } else{ cur += w1; swi[ord[i]]=true; } } if(cur < best){ best = cur; soln.clear(); for(int j = 0 ; j < n; j ++ ){ if(swi[(j + n - 1) % n]) soln.push_back(1); soln.push_back(2); } for(int j = 0; j < shf; j ++ ){ soln.push_back(2); } } } cout << best << "\n"; for(auto x : soln) cout << x; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct! |
2 | Correct | 1 ms | 364 KB | Correct! |
3 | Correct | 1 ms | 512 KB | Correct! |
4 | Correct | 1 ms | 364 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct! |
2 | Correct | 1 ms | 364 KB | Correct! |
3 | Correct | 1 ms | 364 KB | Correct! |
4 | Correct | 1 ms | 364 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 700 KB | Correct! |
2 | Correct | 16 ms | 680 KB | Correct! |
3 | Correct | 17 ms | 704 KB | Correct! |
4 | Correct | 15 ms | 704 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 276 ms | 5136 KB | Correct! |
2 | Correct | 320 ms | 5236 KB | Correct! |
3 | Correct | 707 ms | 10320 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1494 ms | 19012 KB | Correct! |
2 | Correct | 1547 ms | 19004 KB | Correct! |
3 | Correct | 1800 ms | 18880 KB | Correct! |
4 | Correct | 1794 ms | 19044 KB | Correct! |
5 | Correct | 1854 ms | 19068 KB | Correct! |