제출 #946161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946161		NourWael	아름다운 순열 (IZhO12_beauty)	C++17	0 / 100	29 ms	27280 KiB

beauty

#include <bits/extc++.h>
using namespace std; 
using namespace __gnu_pbds; 
int dp[(1<<20)][20][20];
map<int,int> forw, back;
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;
      if(forw.find(cnt)==forw.end()) { forw[cnt] = ind, back[ind] = cnt; ind++; }

      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)][forw[two[i]]][thre[i]] = 1;
   
   for(int mask = 1;  mask<(1<<n); mask++) {
      for(int i=0; i<n; i++) {
         if(mask&(1<<i)) continue;
         // try same two
         for(int j=0; j<20; j++) dp[mask+(1<<i)][forw[two[i]]][thre[i]] += dp[mask][forw[two[i]]][j];
         // try same three
         for(int j=0; j<20; j++) dp[mask+(1<<i)][forw[two[i]]][thre[i]] += dp[mask][j][thre[i]];
         // subtract repeated 
         dp[mask+(1<<i)][forw[two[i]]][thre[i]] -= dp[mask][forw[two[i]]][thre[i]];
      } 
   }

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

• Subtask 1: 0 / 100