답안 #334941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334941 2020-12-10T12:02:52 Z iulia13 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
85 ms 103020 KB
#include <iostream>

using namespace std;
const int doi = (1 << 20);
int dp[doi][25];
struct ura{
    int a, b;
};
ura v[25];
int main()
{
    int n, i, p2 = 1, p3 = 1, j, 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;
            p /= 3;
        }
        dp[(1 << i)][i] = 1;
    }
    for (int mask = 1; mask < doi; 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 103020 KB Output is correct
2 Correct 77 ms 102892 KB Output is correct
3 Incorrect 85 ms 102892 KB Output isn't correct
4 Halted 0 ms 0 KB -