oj.uz

Submission #946161

# Submission time Handle Problem Language Result Execution time Memory
946161 2024-03-14T11:21:48 Z NourWael Beautiful row (IZhO12_beauty) C++17
0 / 100
 29 ms 27280 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Incorrect 29 ms 27280 KB Output isn't correct
12 Halted 0 ms 0 KB -