Submission #89296

#	Time	Username	Problem	Language	Result	Execution time	Memory
89296		abil	Beautiful row (IZhO12_beauty)	C++14	100 / 100	1982 ms	189576 KiB

beauty

/**
   Solution by Abil
**/
# include <bits/stdc++.h>

////////////////////////

# define fr first
# define sc second
# define pb push_back
# define mk make_pair
# define sz(s) s.size()
# define all(s) s.begin(),s.end()
# define int long long

using namespace std;

const long long N = (1e6 + 10);
const long long mod = (1e9 + 7);

vector<pair <int, int> > v;
int arr[N+N],a[21][21],dp[N+N][21];
int f(int x){
   int cnt = 0;
   while(x){
    if(x % 3 == 1){
      cnt++;
    }
    x = x / 3;
   }
   return cnt;
}
main()
{
   int n, x;
   cin >> n;
   for(int i = 1;i <= n; i++){
    cin >> arr[i];
   }
   for(int i = 1;i <= n; i++){
    for(int j = 1;j <= n; j++){
      if(i != j){
        if(__builtin_popcount(arr[i]) == __builtin_popcount(arr[j]) || f(arr[i]) == f(arr[j])){
          a[i][j] = 1;
        }
      }
    }
   }
   int ans = 0;
   for(int i = 0;i < n; i++){
    dp[1 << i][i] = 1;
   }
   for(int i = 0;i < (1<<n); i++){
      v.push_back(make_pair (__builtin_popcount(i),i));
   }
   sort(all(v));

  for(int i=1;i < (1<<n); i++ ){
    for(int j=0;j<=n;j++)
    if((v[i].second & (1<<j))==0){
      for(int k=0;k<=n;k++)
      if((v[i].second & (1<<k)) && a[k+1][j+1]==1){
        dp[ v[i].second | (1<<j)][j] += dp[v[i].second][k];
      }
    }
  }
  for(int i = 0;i <= n; i++)
      ans+=dp[(1<<n)-1][i];

    cout<<ans;

}

Compilation message (stderr)

beauty.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:35:11: warning: unused variable 'x' [-Wunused-variable]
    int n, x;
           ^

• Subtask 1: 100 / 100