Submission #946193

#	Time	Username	Problem	Language	Result	Execution time	Memory
946193		NourWael	Beautiful row (IZhO12_beauty)	C++17	0 / 100	6 ms	2696 KiB

beauty

#include <bits/extc++.h>
using namespace std; 
using namespace __gnu_pbds; 
int dp[(1<<20)][20];
int two[20], thre[20];

signed main() {
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   
   int n; cin>>n;
   int a[20], ind = 0;
   for(int i=0; i<n; i++) {
      cin>>a[i];
      int cnt = 0, x = a[i];
      while(x) {
         cnt += (x&1);
         x = x>>1;
      }
      two[i] = cnt;
      x = a[i], cnt = 0;
      int b = 387420489;
      while(x) {
         if(b*2<=x) { x-=b*2; }
         else if(b<=x) { x-=b; cnt++; }
         b/=3;
      }
      thre[i] = cnt;
   }
   
   for(int i=0; i<n; i++)  dp[(1<<i)][i] = 1;
   
   for(int mask = 1;  mask<(1<<n); mask++) {

      for(int i=0; i<n; i++) {
         if(mask&(1<<i)) continue;
         for(int j=0; j<n; j++) {
            if(mask&(1<<j) && (two[j]==two[i] || thre[j]==thre[i])) dp[mask+(1<<i)][i] += dp[mask][j];
         }
      } 

   }

   int fin = 0;
   for(int i=0; i<n; i++) fin += dp[(1<<n)-1][i];
   cout<<fin;
   return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:11:15: warning: unused variable 'ind' [-Wunused-variable]
   11 |    int a[20], ind = 0;
      |               ^~~

• Subtask 1: 0 / 100