Submission #1179867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179867		Quentolosse	Beautiful row (IZhO12_beauty)	C++20	100 / 100	1364 ms	172872 KiB

beauty

#include <bits/stdc++.h>

#define int long long
using namespace std;


int nb1 (int nombre, int base) {
    int ret = 0;
    int m = 1;
    while (m <= nombre)
    {
        if ((nombre / m) % base == 1) {
            ret++;
        }
        m *= base;
    }

    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    
    vector<int> nombres(n);

    for(auto &&i: nombres) {
        cin >> i;
    }

    vector<vector<bool>> a_cote(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (nb1(nombres[i], 2) == nb1(nombres[j], 2) || nb1(nombres[i], 3) == nb1(nombres[j], 3)) {
                a_cote[i][j] = true;
                a_cote[j][i] = true;
            }
        }
    }

    vector<vector<int>> dp(n, vector<int> (1 << n, 0));
    for(int i = 0; i < n; i++) {
        dp[i][(1 << n) - 1] = 1;
    }
    for(int b = (1 << n) - 2; b > 0; b--) {
        for (int i = 0; i < n; i++)
        {
            for (int d = 0; d < n; d++)
            {
                if ((b >> d) % 2) continue;
                if (a_cote[i][d]) {
                    dp[i][b] += dp[d][b | (1 << d)];
                }
            }
        }
    }

    int reponse = 0;
    for (int i = 0; i < n; i++) {
        reponse += dp[i][1 << i];
    }

    cout << reponse << endl;

}

• Subtask 1: 100 / 100