Submission #41215

#	Time	Username	Problem	Language	Result	Execution time	Memory
41215		MatheusLealV	Beautiful row (IZhO12_beauty)	C++14	0 / 100	3037 ms	173096 KiB

beauty

#include <bits/stdc++.h>
#define N 21
#define M ((1<<20) + 100)
using namespace std;
typedef long long ll;

int n, v[N], qtd[N][5];

ll dp[N][M], pot[45];

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

vector<int> grafo[N];

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(auto v: grafo[x])
	{
		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]);
	}

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(equal(i, j)) grafo[i].push_back(j);

	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