oj.uz

Submission #522058

# Submission time Handle Problem Language Result Execution time Memory
522058 2022-02-03T16:57:13 Z perchuts Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 1964 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

//observation: model the problem to a graph
//count the number of hamiltonian paths.
int v[21];
int cnt2[21],cnt3[21];
ll dp[21][(1<<21)+10];
int count3(int x){
    int resp = 0;
    while(x){
        if(x%3==1)resp++;
        x/=3;
    }
    return resp;
}
int n;
int can[21][21];
ll solve(int cur,int mask){
    if(dp[cur][mask])return dp[cur][mask];
    if(mask==(1<<n)-1)return dp[cur][mask] = 1LL;
    for(int i=0;i<n;i++){
        if((mask&(1<<i))==0&&can[cur][i])dp[cur][mask]+=solve(i,mask|(1<<i));
    }
    return dp[cur][mask];
}

int main(){_
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
        cnt2[i] = __builtin_popcount(v[i]);
        cnt3[i] = count3(v[i]);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j&&(cnt2[i]==cnt2[j]||cnt3[i]==cnt3[j]))can[i][j] = 1;
    
    // for(int i=0;i<n;i++)
    //     for(int j=0;j<n;j++)
    //         cout<<can[i][j]<<" \n"[j==n-1];
    ll ans = 0;
    for(int i=0;i<n;i++)ans += solve(i,1<<i);
    cout<<ans<<endl;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Execution timed out 3060 ms 1964 KB Time limit exceeded
12 Halted 0 ms 0 KB -