oj.uz

답안 #881117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881117 2023-11-30T15:38:05 Z alexdd 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 875 ms 164692 KB 
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int cnt2[25];
int cnt3[25];
long long dp[1100000][20];
int calc_cnt2(int x)
{
    int rez=0;
    for(int i=0;i<30;i++)
    {
        if(((1<<i)&x))
            rez++;
    }
    return rez;
}
int calc_cnt3(int x)
{
    int rez=0;
    while(x>0)
    {
        if(x%3==1)
            rez++;
        x/=3;
    }
    return rez;
}
signed main()
{
    cin>>n;
    int a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        cnt2[i] = calc_cnt2(a);
        cnt3[i] = calc_cnt3(a);
    }
    for(int config=1;config<(1<<n);config++)
    {
        for(int cur=0;cur<n;cur++)
        {
            if(((1<<cur)&config)==0)
                continue;
            int cate=0;
            for(int ult=0;ult<n;ult++)
            {
                if(ult!=cur && ((1<<ult)&config))
                {
                    cate++;
                    if(cnt2[ult]==cnt2[cur] || cnt3[ult]==cnt3[cur])
                    {
                        dp[config][cur] += dp[config-(1<<cur)][ult];
                    }
                }
            }
            if(cate==0)
                dp[config][cur] = 1;
        }
    }
    long long sum=0;
    for(int ult=0;ult<n;ult++)
        sum += dp[(1<<n)-1][ult];
    cout<<sum;
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 452 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 4720 KB Output is correct
12 Correct 8 ms 4700 KB Output is correct
13 Correct 37 ms 10836 KB Output is correct
14 Correct 181 ms 41556 KB Output is correct
15 Correct 154 ms 41576 KB Output is correct
16 Correct 179 ms 41632 KB Output is correct
17 Correct 180 ms 41628 KB Output is correct
18 Correct 183 ms 41556 KB Output is correct
19 Correct 875 ms 164692 KB Output is correct
20 Correct 716 ms 164644 KB Output is correct