Submission #387631

#	Time	Username	Problem	Language	Result	Execution time	Memory
387631		Kevin_Zhang_TW	Cheerleaders (info1cup20_cheerleaders)	C++17	21 / 100	2083 ms	12372 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 <<setw(2) << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 17, inf = 1e9;

int n;
int a[(1<<MAX_N) + 10];

map<vector<int>, string> st;

int cntinv(vector<int> a) {
	vector<int> cnt((1<<n)+1);

	auto qry = [&](int i) {
		++i;
		int res = 0;
		for (;i <= (1<<n);i += i&-i)
			res += cnt[i];
		return res;
	};
	auto add = [&](int i) {
		++i;
		for (;i;i ^= i&-i)
			++cnt[i];
	};
	int res = 0;
	for (int x : a) {
		res += qry(x);
		add(x);
	}
	return res;

}

// 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;
}
void dfs(vector<int> vec, int lev) {

	static string ops;

	if (st.count(vec)) return;

	st[vec] = ops;

	ops += '1';
	dfs(aop(vec), lev);
	++ops.back();
	dfs(bop(vec), lev);
	ops.pop_back();
}

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

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

	vector<int> a(1<<n), tar(1<<n);

	iota(AI(tar), 0);

	for (int &i : a) cin >> i;

	string res;

	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 = inf, 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);
	}

	cout << 0 << '\n' << res << '\n';

}

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