oj.uz

Submission #13349

# Submission time Handle Problem Language Result Execution time Memory
13349 2015-02-13T12:31:45 Z baneling100 Beautiful row (IZhO12_beauty) C++
100 / 100
 1255 ms 173116 KB 
#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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 173116 KB Output is correct
2 Correct 0 ms 173116 KB Output is correct
3 Correct 0 ms 173116 KB Output is correct
4 Correct 0 ms 173116 KB Output is correct
5 Correct 0 ms 173116 KB Output is correct
6 Correct 0 ms 173116 KB Output is correct
7 Correct 0 ms 173116 KB Output is correct
8 Correct 0 ms 173116 KB Output is correct
9 Correct 0 ms 173116 KB Output is correct
10 Correct 0 ms 173116 KB Output is correct
11 Correct 10 ms 173116 KB Output is correct
12 Correct 10 ms 173116 KB Output is correct
13 Correct 44 ms 173116 KB Output is correct
14 Correct 232 ms 173116 KB Output is correct
15 Correct 212 ms 173116 KB Output is correct
16 Correct 211 ms 173116 KB Output is correct
17 Correct 215 ms 173116 KB Output is correct
18 Correct 208 ms 173116 KB Output is correct
19 Correct 1255 ms 173116 KB Output is correct
20 Correct 1245 ms 173116 KB Output is correct