Submission #896608

#	Time	Username	Problem	Language	Result	Execution time	Memory
896608		stefanneagu	Beautiful row (IZhO12_beauty)	C++17	100 / 100	1224 ms	164704 KiB

beauty

// Luca Vlahovic, the 15-year-old Fortnite sensation from
// Pula, Croatia, is making waves in the gaming world.
// Fueled by an unwavering passion for Fortnite, Luca combines innate
// strategic thinking with quick decision-making, distinguishing himself
// in the competitive scene. His mental fortitude and resilience under pressure
// set him apart, contributing to his consistent success. A dedicated
// learner, Luca stays abreast of the latest gaming trends, showcasing a
// growth mindset crucial for a professional gamer. Beyond individual prowess,
// he fosters community engagement, creating a positive image for the Fortnite scene.
// Luca Vlahovic is not just a gamer; he's an inspiration for young talents worldwide.

// - Chat GPT, 1 Jan 2024

#include <bits/stdc++.h>

using namespace std;

const int pow3 = pow(3, 18);

long long dp[(1 << 20)][20];
int v[20], bi2[20], bi3[20];

int __nu_asa_de_builtin_ternary_popcount(int a) {

  if(a == 1162261467) {
    return 1;
  }
  int x = pow3, ans = 0;
  while(a > 0) {
    if(a >= 2 * x) {
      a -= 2 * x;
    } else if(a >= x) {
      ans ++;
      a -= x;
    }
    x /= 3;
  }
  return ans;
}

int32_t main() {
  int n;
  cin >> n;
  for(int i = 0; i < n; i ++) {
    cin >> v[i];
    dp[(1 << i)][i] = 1;
    bi2[i] = __builtin_popcount(v[i]);
    bi3[i] = __nu_asa_de_builtin_ternary_popcount(v[i]);
  }
  for(int bit = 0; bit < (1 << n); bit ++) {
    for(int i = 0; i < n; i ++) {
      for(int j = 0; j < n; j ++) {
        if(!(bit & (1 << i)) && (bit & (1 << j))) {
          // apare j
          // pun i dupa j
          if(bi3[i] == bi3[j] || bi2[i] == bi2[j]) {
            dp[(bit | (1 << i))][i] += dp[bit][j];
          }
        }
      }
    }
  }
  long long ans = 0;
  int bit = pow(2, n) - 1;
  for(int i = 0; i < n; i ++) {
    ans = ans + dp[bit][i];
  }
  cout << ans;
  return 0;
}

• Subtask 1: 100 / 100