Submission #315661

#	Time	Username	Problem	Language	Result	Execution time	Memory
315661		jovan_b	Beautiful row (IZhO12_beauty)	C++17	100 / 100	773 ms	205688 KiB

beauty

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

bool check(int a, int b){
    int x = a, y = b;
    int b1 = 0, b2 = 0;
    while(x){
        b1 += (x%2 == 1);
        x /= 2;
    }
    while(y){
        b2 += (y%2 == 1);
        y /= 2;
    }
    if(b1 == b2) return 1;
    x = a, y = b, b1 = 0, b2 = 0;
    while(x){
        b1 += (x%3 == 1);
        x /= 3;
    }
    while(y){
        b2 += (y%3 == 1);
        y /= 3;
    }
    return b1 == b2;
}

bool moze[25][25];
ll dp[1500005][25];
ll a[25];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<n; i++){
        dp[1<<i][i] = 1;
        for(int j=0; j<n; j++){
            moze[i][j] = check(a[i], a[j]);
        }
    }
    for(int mask=0; mask<(1<<n); mask++){
        for(int i=0; i<n; i++){
            if(!(mask&(1<<i))) continue;
            for(int j=0; j<n; j++){
                if(mask&(1<<j)) continue;
                dp[mask|(1<<j)][j] += dp[mask][i]*moze[i][j];
            }
        }
    }
    ll res = 0;
    for(int i=0; i<n; i++) res += dp[(1<<n)-1][i];
    cout << res;
    return 0;
}

• Subtask 1: 100 / 100