Submission #523467

#	Time	Username	Problem	Language	Result	Execution time	Memory
523467		lukameladze	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	581 ms	172732 KiB

beauty

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
using namespace std;
const int N = 21;
int fix[N][N],lst,ans,lst1,a[N],n,dp[(1<<N)][N];
int ones(int x) {
    int cnt = 0;
    while (x) {
        cnt += ((x%3)==1);
        x/=3;
    }
    return cnt;
}
main() {
    cin>>n;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) {
                fix[i][j] = fix[j][i] = 1;
                continue;
            }
            if (ones(a[i]) == ones(a[j])) {
                fix[i][j] = fix[j][i] = 1;
                continue;
            }
        }
    }
    for (int i = 1; i < (1<<n); i++) {
        vector <int> v;
        for (int j = 0; j < n; j++) {
            if ((1<<j)&i) v.pb(j);
        }
        if (__builtin_popcount(i) == 1){ dp[i][v[0]] = 1; continue; }
        for (int j = 0; j < v.size(); j++) { lst = v[j];
            for (int j1 = 0; j1 < v.size(); j1++) { lst1 = v[j1];
                if (j == j1) continue;
                if (fix[lst][lst1]) {
                dp[i][lst] += dp[i ^ (1<<lst)][lst1];
                }
            }
            if (i == (1<<n) - 1) ans += dp[i][lst];//, ans %= mod;
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

beauty.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main() {
      | ^~~~
beauty.cpp: In function 'int main()':
beauty.cpp:40:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < v.size(); j++) { lst = v[j];
      |                         ~~^~~~~~~~~~
beauty.cpp:41:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (int j1 = 0; j1 < v.size(); j1++) { lst1 = v[j1];
      |                              ~~~^~~~~~~~~~

• Subtask 1: 100 / 100