oj.uz

Submission #31103

# Submission time Handle Problem Language Result Execution time Memory
31103 2017-08-10T00:33:59 Z TAMREF Beautiful row (IZhO12_beauty) C++11
100 / 100
 1516 ms 165860 KB 
#include <bits/stdc++.h>
#define bp __builtin_popcount
using namespace std;
inline int tp(int x){
    int cnt=0;
    for(;x;x/=3) cnt+=(x%3==1);
    return cnt;
}
vector<int> G[20];
int N, a[20];
long long tsp[20][1048576];
void init(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(bp(a[i])==bp(a[j])||tp(a[i])==tp(a[j])){
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    for(int i=0;i<N;i++){
        tsp[i][1<<i]=1;
    }
}
void travel(){
    for(int b=1;b<(1<<N)-1;b++){
        for(int i=0;i<N;i++){
            for(int j : G[i]){
                if((b & 1<<j) ==0){
                    tsp[j][b|(1<<j)]+=tsp[i][b];
                }
            }
        }
    }
}
void debug(){
    for(int i=0;i<N;i++,puts("")) for(int u : G[i]) printf("%d ",u);
    for(int i=0;i<N;i++,puts("")) for(int j=0;j<(1<<N);j++) printf("%d ",tsp[i][j]);
}
int main(){
    init();
    travel();
    long long perm=0;
    for(int i=0;i<N;i++) perm+=tsp[i][(1<<N)-1];
    printf("%lld\n",perm);
    //debug();
}

Compilation message

beauty.cpp: In function 'void debug()':
beauty.cpp:42:83: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     for(int i=0;i<N;i++,puts("")) for(int j=0;j<(1<<N);j++) printf("%d ",tsp[i][j]);
                                                                                   ^
beauty.cpp: In function 'void init()':
beauty.cpp:13:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
beauty.cpp:15:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 165860 KB Output is correct
2 Correct 0 ms 165860 KB Output is correct
3 Correct 0 ms 165860 KB Output is correct
4 Correct 0 ms 165860 KB Output is correct
5 Correct 0 ms 165860 KB Output is correct
6 Correct 0 ms 165860 KB Output is correct
7 Correct 0 ms 165860 KB Output is correct
8 Correct 0 ms 165860 KB Output is correct
9 Correct 0 ms 165860 KB Output is correct
10 Correct 0 ms 165860 KB Output is correct
11 Correct 16 ms 165860 KB Output is correct
12 Correct 9 ms 165860 KB Output is correct
13 Correct 63 ms 165860 KB Output is correct
14 Correct 313 ms 165860 KB Output is correct
15 Correct 306 ms 165860 KB Output is correct
16 Correct 269 ms 165860 KB Output is correct
17 Correct 283 ms 165860 KB Output is correct
18 Correct 239 ms 165860 KB Output is correct
19 Correct 1503 ms 165860 KB Output is correct
20 Correct 1516 ms 165860 KB Output is correct