oj.uz

답안 #1037012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037012 2024-07-27T21:46:51 Z pera 아름다운 순열 (IZhO12_beauty) C++17
0 / 100
 50 ms 262144 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 21 , LOG = 30;
int n;
vector<int> a(N);
vector<vector<int>> dp(N , vector<int>(1 << N)) , v2(LOG) , v3(LOG) , v(N);
int ternary_ones(int x){
   int cnt = 0;
   while(x > 0){
      cnt += (x % 3 == 1);
      x /= 3;
   }
   return cnt;
}
main(){
  cin >> n;
  for(int i = 1;i <= n;i ++){
     cin >> a[i];
     v2[__builtin_popcount(a[i])].push_back(i);
     v3[ternary_ones(a[i])].push_back(i);
  }
  for(int i = 1;i <= n;i ++){
     for(int x : v2[__builtin_popcount(a[i])]){
        if(x != i){
           v[i].push_back(x);
        }
     }
     for(int x : v3[ternary_ones(a[i])]){
        if(x != i){
           v[i].push_back(x);
        }
     }
     v[i].push_back(0);
  }
  dp[0][0] = 1;
  for(int mask = 0;mask < (1 << n);mask ++){
     for(int x = 1;x <= n;x ++){
        if(mask >> (x - 1) & 1){
           for(int y : v[x]){
              if(y == 0 || (mask >> (y - 1) & 1)){
                 dp[x][mask] += dp[y][mask ^ (1 << (x - 1))];
              }
           }
        }
     }
  }
  int ans = 0;
  for(int x = 1;x <= n;x ++){
     ans += dp[x][(1 << n)- 1];
  }
  cout << ans << endl;
}

Compilation message

beauty.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -