oj.uz

Submission #946193

# Submission time Handle Problem Language Result Execution time Memory
946193 2024-03-14T11:55:01 Z NourWael Beautiful row (IZhO12_beauty) C++17
0 / 100
 6 ms 2696 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 6 ms 2696 KB Output isn't correct
12 Halted 0 ms 0 KB -