oj.uz

Submission #89818

# Submission time Handle Problem Language Result Execution time Memory
89818 2018-12-18T13:07:02 Z Vardanyan Beautiful row (IZhO12_beauty) C++14
100 / 100
 1214 ms 181304 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 22;
int a[N];
bool d[N][N];
bool check(int x,int y){
    int xx,yy;
    xx = yy = 0;
    for(int i = 0;i<32;i++){
        if((x>>i)&1) xx++;
        if((y>>i)&1) yy++;
    }
    if(xx == yy) return true;
    xx = yy = 0;
    while(x!=0){
        if(x%3 == 1) xx++;
        x/=3;
    }
    while(y!=0){
        if(y%3 == 1) yy++;
        y/=3;
    }
    return xx == yy;
}
long long dp[(1<<N)][N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++) cin>>a[i];
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            if(check(a[i],a[j])){
                d[i][j] = d[j][i] = 1;
            }
        }
        dp[(1<<i)][i] = 1;
    }
    for(int mask = 1;mask<(1<<n);mask++){
        for(int lst = 0;lst<n;lst++){
            if(!((mask>>lst)&1)) continue;
            for(int i = 0;i<n;i++){
                if((mask>>i)&1) continue;
                if(d[lst][i]){
                    dp[mask|(1<<i)][i]+=dp[mask][lst];
                }
            }
        }
    }
    long long ans = 0;
    for(int lst = 0;lst<n;lst++) ans+=dp[(1<<n)-1][lst];
    cout<<ans<<endl;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 804 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 804 KB Output is correct
11 Correct 12 ms 3392 KB Output is correct
12 Correct 11 ms 3436 KB Output is correct
13 Correct 48 ms 11896 KB Output is correct
14 Correct 265 ms 45688 KB Output is correct
15 Correct 231 ms 45716 KB Output is correct
16 Correct 231 ms 45716 KB Output is correct
17 Correct 234 ms 45868 KB Output is correct
18 Correct 240 ms 45872 KB Output is correct
19 Correct 1214 ms 181256 KB Output is correct
20 Correct 1092 ms 181304 KB Output is correct