oj.uz

Submission #89296

# Submission time Handle Problem Language Result Execution time Memory
89296 2018-12-11T14:57:45 Z abil Beautiful row (IZhO12_beauty) C++14
100 / 100
 1982 ms 189576 KB 
/**
   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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 3 ms 628 KB Output is correct
8 Correct 3 ms 812 KB Output is correct
9 Correct 3 ms 812 KB Output is correct
10 Correct 3 ms 812 KB Output is correct
11 Correct 16 ms 3628 KB Output is correct
12 Correct 16 ms 3756 KB Output is correct
13 Correct 82 ms 12660 KB Output is correct
14 Correct 412 ms 47832 KB Output is correct
15 Correct 410 ms 47920 KB Output is correct
16 Correct 445 ms 48076 KB Output is correct
17 Correct 434 ms 48076 KB Output is correct
18 Correct 458 ms 48076 KB Output is correct
19 Correct 1982 ms 189576 KB Output is correct
20 Correct 1911 ms 189576 KB Output is correct