oj.uz

Submission #387703

# Submission time Handle Problem Language Result Execution time Memory
387703 2021-04-09T05:54:49 Z Kevin_Zhang_TW Cheerleaders (info1cup20_cheerleaders) C++17
100 / 100
 749 ms 15708 KB 
#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;

// swap left right
vector<int> aop(vector<int> vec) {
	vector<int> a;
	int m = vec.size();
	{
		// A
		for (int i = m/2;i < m;++i)
			a.pb(vec[i]);
		for (int i = 0;i < m/2;++i)
			a.pb(vec[i]);
	}
	return a;
}
// odd and even
vector<int> bop(vector<int> vec) {
	vector<int> b;

	int m = vec.size();
	{
		// B
		for (int i = 0;i < m;i += 2)
			b.pb(vec[i]);
		for (int i = 1;i < m;i += 2)
			b.pb(vec[i]);
	}

	return b;
}

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;
	}
}

int BBB;

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

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

	BBB = min_element(dp, dp + (1<<n)) - dp;

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

int tmp[1<<MAX_N];

string recover(vector<int> a) {
	string res;

	vector<int> tar(1<<n); iota(AI(tar), 0);

	while (a[0]) {
		vector<vector<int>> cand;
		{
			auto now = a;
			for (int i = 0;i < n;++i) {
				cand.pb(now);
				now = bop(now);
			}
		}
		int mnv = 2 << n, pos = -1;
		for (int i = 0;i < n;++i) {
			if (chmin(mnv, cand[i][(1<<(n-1))]))
				pos = i;
		}
		res += string(pos, '2');

		a = cand[pos];

		res += '1';

		a = aop(a);
	}

	while (a != tar) {
		res += '2';
		a = bop(a);
	}

	return res;
}

vector<int> build(int T, int V) {
	vector<int> res;

	
	{
		int turn = n - T;

		while (turn--) 
			V = V >> 1 | ((V&1) << (n-1));
	}

	DE(T, V);

	res.pb(V);

	for (int i = 0;i < n;++i) {
		int nb = (T + i) % n;

		int osz = res.size();
		for (int i = 0;i < osz;++i) {
			res.pb(res[i] ^ (1<<nb));
		}
	}

	vector<int> trans(1<<n);

	for (int i = 0;i < 1<<n;++i)
		trans[ res[i] ] = i;

	return trans;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;

	if (n == 0) return cout << "0\n\n", 0;

	for (int i = 0;i < 1<<n;++i)
		cin >> a[i];

	ll res = inf;

	DE(cal());


	int T = -1, V = -1;

	for (int i = 0;i < n;++i) {
		if (chmin(res, cal())) {
			T = i, V = BBB;
		}
		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';

	auto vec = build(T, V);

	cout << recover(vec) << '\n';
}

Compilation message

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 1 ms 332 KB Correct!
3 Correct 1 ms 332 KB Correct!
4 Correct 1 ms 332 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct!
2 Correct 1 ms 332 KB Correct!
3 Correct 1 ms 332 KB Correct!
4 Correct 1 ms 332 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Correct!
2 Correct 6 ms 528 KB Correct!
3 Correct 6 ms 460 KB Correct!
4 Correct 5 ms 520 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3852 KB Correct!
2 Correct 92 ms 3960 KB Correct!
3 Correct 126 ms 7640 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 15696 KB Correct!
2 Correct 413 ms 15680 KB Correct!
3 Correct 691 ms 15672 KB Correct!
4 Correct 749 ms 15708 KB Correct!
5 Correct 666 ms 15560 KB Correct!