oj.uz

Submission #89294

# Submission time Handle Problem Language Result Execution time Memory
89294 2018-12-11T14:56:30 Z abil Beautiful row (IZhO12_beauty) C++14
0 / 100
 1420 ms 263168 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],a[21][21],dp[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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 652 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 788 KB Output is correct
8 Correct 3 ms 788 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 3 ms 788 KB Output is correct
11 Correct 16 ms 3636 KB Output is correct
12 Correct 16 ms 3636 KB Output is correct
13 Correct 73 ms 12564 KB Output is correct
14 Correct 354 ms 48080 KB Output is correct
15 Correct 409 ms 48080 KB Output is correct
16 Correct 452 ms 48080 KB Output is correct
17 Correct 386 ms 48136 KB Output is correct
18 Correct 376 ms 48136 KB Output is correct
19 Runtime error 1420 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -