oj.uz

Submission #1037018

# Submission time Handle Problem Language Result Execution time Memory
1037018 2024-07-27T22:00:41 Z pera Beautiful row (IZhO12_beauty) C++17
100 / 100
 628 ms 172892 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 172660 KB Output is correct
2 Correct 32 ms 172628 KB Output is correct
3 Correct 36 ms 172684 KB Output is correct
4 Correct 34 ms 172628 KB Output is correct
5 Correct 35 ms 172628 KB Output is correct
6 Correct 34 ms 172628 KB Output is correct
7 Correct 39 ms 172628 KB Output is correct
8 Correct 35 ms 172628 KB Output is correct
9 Correct 35 ms 172628 KB Output is correct
10 Correct 37 ms 172660 KB Output is correct
11 Correct 38 ms 172828 KB Output is correct
12 Correct 43 ms 172664 KB Output is correct
13 Correct 61 ms 172892 KB Output is correct
14 Correct 159 ms 172624 KB Output is correct
15 Correct 154 ms 172636 KB Output is correct
16 Correct 142 ms 172636 KB Output is correct
17 Correct 151 ms 172628 KB Output is correct
18 Correct 113 ms 172832 KB Output is correct
19 Correct 563 ms 172620 KB Output is correct
20 Correct 628 ms 172664 KB Output is correct