Submission #1233114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233114		fermat	Beautiful row (IZhO12_beauty)	C++20	100 / 100	784 ms	205616 KiB

beauty

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 25;

int n, a[N], sik[N][N];

long long ans, dp[ (1 << 20) + 5 ][N];

main() 
{
 cin >> n;
 for (int i = 0; i < n; i++)
  scanf("%d", &a[i]);
  
 for (int i = 0; i < n; i++)
 {
  int c2 = 0, c3 = 0, x = a[i];
  
  while (x){
   if (x & 1)
    c2++;
   x /= 2;
  }
  x = a[i];
  while (x){
   if (x % 3 == 1)
    c3++;
   x /= 3;
  }
  
  for (int j = i + 1; j < n; j++)
  {
   int cc2 = 0, cc3 = 0;
   x = a[j];
   
   while (x){
    if (x & 1)
     cc2++;
    x /= 2;
   }
   x = a[j];
   while (x){
    if (x % 3 == 1)
     cc3++;
    x /= 3;
   }
   if (cc2 == c2 || cc3 == c3)
    sik[i][j] = sik[j][i] = 1;
  }
 }
 for (int j = 0; j < n; j++)
  dp[1 << j][j] = 1;
  
 for (int mask = 1; mask < (1 << n); mask++)
 {
  for (int last = 0; last < n; last++)
  {
   if ( (mask & (1 << last) ) == 0 ) continue;
   
   for (int nxt = 0; nxt < n; nxt++){
    
    if ( ( mask & (1 << nxt) ) || sik[last][nxt] == 0 ) continue;
    
    dp[mask + (1 << nxt)][nxt] += dp[mask][last];
   }
  }
 }
 for (int i = 0; i < n; i++)
  ans += dp[ (1 << n) - 1 ][i];
  
 cout << ans << endl;
}

Compilation message (stderr)

beauty.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main()
      | ^~~~
beauty.cpp: In function 'int main()':
beauty.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100