Submission #41194

#	Time	Username	Problem	Language	Result	Execution time	Memory
41194		wzy	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2662 ms	165108 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
int adj[30] , v[30] , n , m ;
long long dp[20][1<<20] , maxi;

pair<int,int> f(int x){
	int z1 , z2 , a1 = 0 , a2 = 0;
	z1 = x, z2 = x;
	while(z1 > 0){
		if(z1%2 == 1) a1++;
		z1/=2;
	}
	while(z2 > 0){
		if(z2%3 == 1)a2++;
		z2/=3;
	}
	return pair<int,int>(a1 , a2);
}

long long  solve(int i , int j){
	if(dp[i][j] != -1) return dp[i][j];
	if(j == maxi) return 1;
	dp[i][j] = 0;
	for(int w = 0 ; w < n; w++){
		if(1<<w & j) continue;
		if(1<<w & adj[i]) dp[i][j] += solve(w , j | 1<<w);
	}
	return dp[i][j];
}

int main(){
	cin>>n;
	for(int i = 0 ; i < n ; i++){
		cin>>v[i];
		adj[i] = 0;
	}
	maxi = 1<<n;
	maxi--;
	for(int i = 0 ; i < n;i ++){
		for(int j = i + 1 ; j <n ; j++){
			if(f(v[i]).first == f(v[j]).first || f(v[i]).second == f(v[j]).second){
				adj[i] |= 1<<j;
				adj[j] |= 1<<i;
			}
		}
	}
	memset(dp , -1 , sizeof dp);
	long long ans = 0;
	for(int i = 0 ; i < n; i++)  ans+= solve(i , 1<<i);
	cout<<ans<<endl;
}

• Subtask 1: 100 / 100