Submission #1037018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037018		pera	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	628 ms	172892 KiB

beauty

#include<bits/stdc++.h>
using namespace std;
const int N = 20 , LOG = 30;
int n;
vector<int> a(N);
vector<vector<long long>> dp(N , vector<long long>(1 << N));
vector<vector<int>> v(N);
int t_o_c(int x){
   int cnt = 0;
   while(x > 0){
      cnt += (x % 3 == 1);
      x /= 3;
   }
   return cnt;
}
int main(){
  cin >> n;
  for(int i = 0;i < n;i ++){
     cin >> a[i];
  }
  for(int x = 0;x < n;x ++){
     for(int y = 0;y < n;y ++){
        if(x != y && (__builtin_popcount(a[x]) == __builtin_popcount(a[y]) || t_o_c(a[x]) == t_o_c(a[y]))){
           v[x].push_back(y);
        }
     }
     dp[x][1 << x] = 1LL;
  }
  for(int mask = 0;mask < (1 << n);mask ++){
     for(int x = 0;x < n;x ++){
        if(mask >> x & 1){
           for(int y : v[x]){
              if(mask >> y & 1){
                 dp[x][mask] += dp[y][mask ^ (1 << x)];
              }
           }
        }
     }
  }
  long long ans = 0;
  for(int i = 0;i < n;i ++){
     ans += dp[i][(1 << n) - 1];
  }
  cout << ans << endl;
}

• Subtask 1: 100 / 100