Submission #335374

#	Time	Username	Problem	Language	Result	Execution time	Memory
335374		iulia13	Beautiful row (IZhO12_beauty)	C++14	100 / 100	1044 ms	205804 KiB

beauty

#include <iostream>
 
using namespace std;
const int doi = (1 << 20);
long long dp[doi][25];
struct ura{
    int a, b;
};
ura v[25];
int main()
{
    int n, i, p2 = 1, p3 = 1, j;
    long long ans = 0;
    cin >> n;
    for (i = 1; i <= 18; i++)
        p3 *= 3;
    p2 = (1 << 30);
    for (i = 0; i < n; i++)
    {
        int nr, cnr;
        cin >> nr;
        cnr = nr;
        int p = p2;
        while (nr)
        {
            if (nr >= p)
            {
                v[i].a++;
                nr -= p;
            }
            p /= 2;
        }
        nr = cnr;
        p = p3;
        while (nr)
        {
            if (nr >= p)
            {
                v[i].b++;
                nr -= p;
            }
            if (nr >= p)
            {nr -= p; v[i].b--;}
            p /= 3;
        }
        dp[(1 << i)][i] = 1;
    }
    for (int mask = 1; mask < (1 << n); mask++)
        for (i = 0; i < n; i++)
            if (mask & (1 << i))
                for (j = 0; j < n; j++)
                    if (i != j && (mask & (1 << j)))
                    {
                        if (v[i].a == v[j].a || v[j].b == v[i].b)
                            dp[mask][i] += dp[mask ^ (1 << i)][j];
                    }
    for (i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100