oj.uz

답안 #889849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889849 2023-12-20T08:09:35 Z heeheeheehaaw 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 937 ms 172672 KB 
#include <iostream>
#define int long long

using namespace std;

long long dp[1049000][21];
int v[25], nrr2[25], nrr3[25];

int nr2(int n)
{
    int nr = 0;
    while(n >= 1)
    {
        if(n % 2 == 1)
            nr++;
        n /= 2;
    }

    return nr;
}

int nr3(int n)
{
    int nr = 0;
    while(n >= 1)
    {
        if(n % 3 == 1)
            nr++;
        n /= 3;
    }

    return nr;
}

signed main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)
        cin>>v[i], nrr2[i] = nr2(v[i]), nrr3[i] = nr3(v[i]);

    for(int mask = 1; mask < (1 << n); mask++)
    {
        int nr = 0, b = 0;
        for(int i = 0; i < n; i++)
            if(((1 << i) & mask) != 0)
                nr++, b = i;
        if(nr == 1)
        {
            dp[mask][b] = 1;
        }
        else
        {
            for(int i = 0; i < n; i++)
            {
                if(((1 << i) & mask) != 0)
                {
                    for(int j = 0; j < n; j++)
                    {
                        if(((1 << j) & (mask ^ (1 << i))) == 0)
                            continue;
                        if(nrr3[j] == nrr3[i] || nrr2[j] == nrr2[i])
                        {
                            dp[mask][i] += dp[(mask ^ (1 << i))][j];
                        }
                    }
                }
            }
        }
    }

    int rez = 0;
    for(int i = 0; i < n; i++)
        rez += dp[(1 << n) - 1][i];
    cout<<rez;
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 9 ms 4700 KB Output is correct
12 Correct 11 ms 4720 KB Output is correct
13 Correct 43 ms 12908 KB Output is correct
14 Correct 200 ms 43600 KB Output is correct
15 Correct 198 ms 43600 KB Output is correct
16 Correct 201 ms 43632 KB Output is correct
17 Correct 198 ms 43628 KB Output is correct
18 Correct 206 ms 43600 KB Output is correct
19 Correct 937 ms 172644 KB Output is correct
20 Correct 900 ms 172672 KB Output is correct