Submission #1037012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037012		pera	Beautiful row (IZhO12_beauty)	C++17	0 / 100	50 ms	262144 KiB

beauty

#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 (stderr)

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

• Subtask 1: 0 / 100