oj.uz

답안 #41213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41213 2018-02-14T03:17:44 Z MatheusLealV 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 125 ms 172792 KB 
#include <bits/stdc++.h>
#define N 21
#define M ((1<<20) + 100)
using namespace std;
typedef long long ll;

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

ll dp[N][M];

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 172792 KB Output is correct
2 Incorrect 125 ms 172792 KB Output isn't correct
3 Halted 0 ms 0 KB -