# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
13349 | baneling100 | 아름다운 순열 (IZhO12_beauty) | C++98 | 1255 ms | 173116 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#define N_MAX 20
#define BIT_MAX 1048575
int N, M=1, A[N_MAX+1], B[N_MAX+1][N_MAX+1];
long long D[N_MAX+1][BIT_MAX+1], Ans;
int binaryOne(int num) {
int i, cnt=0;
for(i=1 ; i<=num ; i<<=1)
if(num&i)
cnt++;
return cnt;
}
int ternaryOne(int num) {
int cnt=0;
while(num) {
if(num%3==1)
cnt++;
num/=3;
}
return cnt;
}
int main(void) {
int i, j, k;
scanf("%d",&N);
for(i=1 ; i<=N ; i++)
scanf("%d",&A[i]);
for(i=1 ; i<=N ; i++)
for(j=1 ; j<=N ; j++)
if(i!=j && (binaryOne(A[i])==binaryOne(A[j]) || ternaryOne(A[i])==ternaryOne(A[j])))
B[i][j]=1;
for(i=1 ; i<=N ; i++) {
M<<=1;
D[i][1<<(i-1)]=1;
}
M--;
for(i=1 ; i<=M ; i++)
for(j=1 ; j<=N ; j++)
if(i&(1<<(j-1)))
for(k=1 ; k<=N ; k++)
if(B[j][k] && i&(1<<(k-1)))
D[j][i]+=D[k][i-(1<<(j-1))];
for(i=1 ; i<=N ; i++)
Ans+=D[i][M];
printf("%lld",Ans);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |