Submission #387682

#	Time	Username	Problem	Language	Result	Execution time	Memory
387682		Kevin_Zhang_TW	Cheerleaders (info1cup20_cheerleaders)	C++17	46 / 100	582 ms	3144 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(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 debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 17;

const ll inf = 1ll << 40;

ll pre[MAX_N][1<<MAX_N];
int n;

int a[1<<MAX_N], b[1<<MAX_N];

ll dp[1<<MAX_N];

void solve(int l, int r) {
	if (l == r) {
		dp[l] = 0;
		return;
	}

	int mid = l + r >> 1;

	solve(l, mid), solve(mid+1, r);

	ll inv = 0;
	// cnt howmany left bigger than right;

	for (int i = l, j = mid;i <= mid;++i) {
		while (j < r && b[j+1] < b[i])
			++j;
		inv += j - mid;
	}

	inplace_merge(b+l, b+mid+1, b+r+1);

	ll len = r - l + 1, all = (len/2) * (len/2), L = inv, R = all - L;

	int bit = len / 2;

	for (int i = l;i <= mid;++i) {

		ll a = dp[i], b = dp[i | bit];

		dp[i] = a + b + L;

	   	dp[i | bit] = a + b + R;
	}

}

ll cal() {
	for (int i = 0;i < 1<<n;++i) b[i] = a[i];

	solve(0, (1<<n)-1);

	return *min_element(dp, dp + (1<<n));
}

int tmp[1<<MAX_N];

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < 1<<n;++i)
		cin >> a[i];

	ll res = inf;

#define bt(v) bitset<4>(v).to_string()

	DE(cal());

	for (int i = 0;i < n;++i) {
		chmin(res, cal());
		for (int j = 0;j < 1<<n;++j) {
			int nv = j >> 1 | ((j&1) << (n-1));
			tmp[nv] = a[j];
		}
		for (int j = 0;j < 1<<n;++j)
			a[j] = tmp[j];
	}

	cout << res << '\n';
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void solve(int, int)':
cheerleaders.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int mid = l + r >> 1;
      |            ~~^~~
cheerleaders.cpp: In function 'int32_t main()':
cheerleaders.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cheerleaders.cpp:85:2: note: in expansion of macro 'DE'
   85 |  DE(cal());
      |  ^~

• Subtask 1: 0 / 16
• Subtask 2: 5 / 10
• Subtask 3: 20 / 25
• Subtask 4: 0 / 21
• Subtask 5: 21 / 28