답안 #236701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236701 2020-06-03T01:47:28 Z mohamedsobhi777 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
129 ms 262148 KB
#include<bits/stdc++.h>

using namespace std ; 

const int N =20 + 1 ; 

int n; 
int r2[N] , r3[N] ; 
int a[N] ; 
vector<int> p ; 
long long dp[N][(1<<N) + 7] ; 

int solve1(int x , int base){
        int ret = 0 ; 
        while(x){
                ret+= (x%base==1) ; 
                x/=base ; 
        }

        return ret ; 
}
vector<int> adj[N] ; 

long long solve(int x , int mask){
        if(dp[x][mask]!= -1)
                return dp[x][mask] ; 
        if(mask == (1<<n) -1){
                return 1LL ; 
        }
        long long ret = 0 ;
        for(auto u : adj[x]){
                if(mask&(1<<u))
                        continue ; 
                ret += solve(u , (mask|(1<<u))) ; 
        }
        return dp[x][mask] = ret ; 
}

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ;
        //freopen("in.in" , "r" , stdin) ; 
        cin>>n ; 
        memset(dp , -1 , sizeof dp) ; 
        for(int i = 0 ;i < n;i++){
                cin>>a[i] ; 
                r2[i] = solve1(a[i] , 2) ; 
                r3[i] = solve1(a[i] , 3) ; 
        }
        for(int i = 0 ;i < n;i++){
                p.push_back(i) ; 
        }
        for(int i = 0 ;i < n;i++){
                for(int j = i+1 ;j < n;j++){
                        if(r2[i] == r2[j] || r3[i] == r3[j]){
                                adj[i].push_back(j) ; 
                                adj[j].push_back(i) ; 
                        }
                }
        }

        long long ans = 0 ; 
        for(int i = 0 ;i < n;i++){
                ans += solve(i , (1<<i)) ; 
        }
        cout<< ans ; 
        return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 129 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -