Submission #400405

#	Time	Username	Problem	Language	Result	Execution time	Memory
400405		Habitus	Beautiful row (IZhO12_beauty)	C++14	0 / 100	3106 ms	178824 KiB

beauty

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, a[22];
ll dp[1100000][22];
bool mogu(int pr, int dr) {
    pr=a[pr]; dr=a[dr];
    if(__builtin_popcount(pr)==__builtin_popcount(dr)) return true;
    int tn1=0, tn2=0;
    int m1=pr, m2=dr;
    while(m1>0) {
        int cif=m1%3;
        m1/=3;
        if(cif==1) ++tn1;
    }
    while(m2>0) {
        int cif=m2%3;
        m2/=3;
        if(cif==1) ++tn2;
    }
    return (tn1==tn2);
}
int main() {
    ios;
    cin >> n;
    for(int i=0; i<n; ++i) cin >> a[i];
    for(int i=0; i<n; ++i) dp[0][i]=1;
    for(int mask=1; mask<(1<<n); ++mask) {
        for(int last=0; last<n; ++last) {
            if(((1<<last)&mask)==0) continue;
            if(__builtin_popcount(mask)==1) {
                dp[mask][last]=1;
                continue;
            }
            for(int j=0; j<n; ++j) {
                if(j==last || ((1<<j)&mask)==0) continue;
                if(mogu(j, last)) dp[mask][last]+=dp[mask^(1<<last)][j];
            }
        }
    }
    ll suma=0LL;
    for(int i=0; i<n; ++i) suma+=dp[(1<<n)-1][i];
    cout << suma;
    return 0;
}

• Subtask 1: 0 / 100