제출 #41212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41212		MatheusLealV	아름다운 순열 (IZhO12_beauty)	C++14	0 / 100	3029 ms	173424 KiB

beauty

#include <bits/stdc++.h>
#define N 21
#define M 1050000
using namespace std;
typedef long long ll;

ll n, dp[N][M], v[N], pot[45], qtd[N][5];

vector<int> grafo[N];

bool equal(int a, int b)
{
	return (qtd[a][2] == qtd[b][2] || qtd[a][3] == qtd[b][3]);
}

int ternary(int x)
{
	int cnt = 0;

	for(int log3 = 30; log3 >= 0; log3 --)
	{
		ll aux = pot[log3], qaux = 0;

		if(x >= aux)
		{
			x -= aux;

			qaux ++;
		}

		if(x >= aux)
		{
			x -= aux;

			qaux ++;
		}

		cnt = cnt + (qaux == 1);
	}

	return cnt;
}

ll solve(int x, int mask)
{
	if(dp[x][mask] != -1) return dp[x][mask];

	if(mask == (1<<n) - 1) return 1;

	dp[x][mask] = 0;

	for(int v = 0; v < n; v++)
	{
		if(mask & (1<<v)) continue;

		if(equal(x, v)) dp[x][mask] += solve(v, mask | (1<<v));
	}

	return dp[x][mask];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

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

	pot[0] = 1;

	for(int i = 1; i < 45; i++) pot[i] = pot[i - 1]*3;

	for(int i = 0; i < n; i++)
	{
		qtd[i][2] = __builtin_popcount (v[i]);

		qtd[i][3] = ternary(v[i]);
	}

	memset(dp, -1, sizeof dp);

	ll best = 0;

	for(int i = 0; i < n; i++) best += solve(i, 1<<i);

	cout<<best<<"\n";
}

• Subtask 1: 0 / 100