Submission #20905

#	Time	Username	Problem	Language	Result	Execution time	Memory
20905		jjwdi0	아름다운 순열 (IZhO12_beauty)	C++11	100 / 100	2249 ms	165860 KiB

beauty

#include <bits/stdc++.h>
#define pcnt __builtin_popcount
using namespace std;
typedef long long ll;

ll D[1<<20][20];
int N, A[22], B[22], C[22];

int f(int x) {
    if(x <= 2) return x == 1;
    return (x % 3 == 1) + f(x / 3);
}

ll dp(int state, int x) {
    if(~D[state][x]) return D[state][x];
    D[state][x] = 0;
    if(pcnt(state) == 1) return D[state][x] = !!(state & (1 << x));
    for(int i=0; i<N; i++) {
        if(x == i || !((1 << i) & state)) continue;
        if((state & (1 << i)) && (B[x] == B[i] || C[x] == C[i])) D[state][x] += dp(state ^ (1 << x), i);
    }
    return D[state][x];
}

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d", A+i);
    for(int i=0; i<N; i++) B[i] = pcnt(A[i]);
    for(int i=0; i<N; i++) C[i] = f(A[i]);
    memset(D, -1, sizeof(D));
    ll ans = 0LL;
    for(int i=0; i<N; i++) ans += dp((1 << N) - 1, i);
    printf("%lld\n", ans);
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:26:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
beauty.cpp:27:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<N; i++) scanf("%d", A+i);
                                            ^

• Subtask 1: 100 / 100