제출 #4800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4800		tncks0121	아름다운 순열 (IZhO12_beauty)	C++98	100 / 100	1816 ms	164928 KiB

beauty

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 20;
int N, A[N_];
bool G[N_][N_];
int B[N_], C[N_];
ll Table[N_][1<<N_];

int main() {
	int i, j, k;

	scanf("%d", &N);
	for(i = 0; i < N; i++) scanf("%d", A+i);

	for(i = 0; i < N; i++) {
		for(j = A[i]; j > 0; j /= 2) if(j % 2 == 1) ++B[i];
		for(j = A[i]; j > 0; j /= 3) if(j % 3 == 1) ++C[i];
	}

	for(i = 0; i < N; i++) for(j = i+1; j < N; j++) 
		G[i][j] = G[j][i] = (B[i] == B[j] || C[i] == C[j]);

	for(i = 0; i < N; i++) Table[i][1<<i] = 1;

	for(int state = 1; state < (1<<N); state++) {
		for(i = 0; i < N; i++) if(state & (1<<i)) {
			int prev = state ^ (1<<i);
			for(j = 0; j < N; j++) if((prev & (1<<j)) && G[j][i]) Table[i][state] += Table[j][prev];
		}
	}

	ll res = 0;
	for(i = 0; i < N; i++) res += Table[i][(1<<N)-1];
	printf("%lld\n", res);
	return 0;
}

• Subtask 1: 100 / 100