oj.uz

답안 #1098484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098484 2024-10-09T12:50:45 Z 0pt1mus23 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 7 ms 4308 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ins insert      
#define pb push_back

#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));

const int mod = 998244353,
        sze = (1<<20) +23,
        inf = LLONG_MAX,    
        L = 31;

int dp[sze][30];
int bt(int n){
    int c=0;
    while(n){
        c+= ( (n%3) ==1);
        n/=3;
    }
    return c;
}
void _0x0(){
    int n;
    cin>>n;
    vector<int> olur[n];
    vector<int> arr(n);
    vector<int> bar(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
        bar[i]=bt(arr[i]);
        olur[i].resize(n,0);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(bar[i]==bar[j] || __builtin_popcount(arr[i]) == __builtin_popcount(arr[j]) ){
                olur[i][j]=1;
            }
        }
    }
    // dp[0][0]=1;
    for(int i=0;i<n;i++){
        dp[(1<<i)][i] = 1;
    }
    for(int mask=0;mask<(1<<n);mask++){
        for(int last=0;last<n;last++){
            if(mask & (1<<last)){
                for(int ext=0;ext<n;ext++){
                    if(! (mask & (1<<ext)) && olur[last][ext]){
                        // cout<<mask _ " last: " _ last _ "next:" _ ext _ "=>" _ (mask|(1<<ext)) _ dp[mask][last] <<endl;
                        dp[mask | (1<<ext)][ext] += dp[mask][last];
                    }
                }

            }
        }
    }

    int ans=accumulate(dp[(1<<n) -1],dp[(1<<n) -1]+n+1,0);
    putr(ans);

}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin>>tt;
    while(tt--){
        _0x0();
    }
 
    return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Incorrect 7 ms 4308 KB Output isn't correct
12 Halted 0 ms 0 KB -