제출 #387623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387623		Kevin_Zhang_TW	Cheerleaders (info1cup20_cheerleaders)	C++17	26 / 100	2115 ms	1048580 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;

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;

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

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

	dfs(a, 0);

	int res = INT_MAX;
	string ops;
	for (auto [q, str] : st) {
		auto vec = q;
		if (chmin(res, cntinv(vec)))
			ops = str;
	}

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

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