oj.uz

Submission #236702

# Submission time Handle Problem Language Result Execution time Memory
236702 2020-06-03T01:48:32 Z mohamedsobhi777 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2490 ms 164732 KB 
#include<bits/stdc++.h>

using namespace std ; 

const int N =20 ; 

int n; 
int r2[N] , r3[N] ; 
int a[N] ; 
vector<int> p ; 
long long dp[N][(1<<N)] ; 

int solve1(int x , int base){
        int ret = 0 ; 
        while(x){
                ret+= (x%base==1) ; 
                x/=base ; 
        }

        return ret ; 
}
vector<int> adj[N] ; 

long long solve(int x , int mask){
        if(dp[x][mask]!= -1)
                return dp[x][mask] ; 
        if(mask == (1<<n) -1){
                return 1LL ; 
        }
        long long ret = 0 ;
        for(auto u : adj[x]){
                if(mask&(1<<u))
                        continue ; 
                ret += solve(u , (mask|(1<<u))) ; 
        }
        return dp[x][mask] = ret ; 
}

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ;
        //freopen("in.in" , "r" , stdin) ; 
        cin>>n ; 
        memset(dp , -1 , sizeof dp) ; 
        for(int i = 0 ;i < n;i++){
                cin>>a[i] ; 
                r2[i] = solve1(a[i] , 2) ; 
                r3[i] = solve1(a[i] , 3) ; 
        }
        for(int i = 0 ;i < n;i++){
                p.push_back(i) ; 
        }
        for(int i = 0 ;i < n;i++){
                for(int j = i+1 ;j < n;j++){
                        if(r2[i] == r2[j] || r3[i] == r3[j]){
                                adj[i].push_back(j) ; 
                                adj[j].push_back(i) ; 
                        }
                }
        }

        long long ans = 0 ; 
        for(int i = 0 ;i < n;i++){
                ans += solve(i , (1<<i)) ; 
        }
        cout<< ans ; 
        return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164472 KB Output is correct
2 Correct 79 ms 164472 KB Output is correct
3 Correct 78 ms 164472 KB Output is correct
4 Correct 80 ms 164732 KB Output is correct
5 Correct 80 ms 164600 KB Output is correct
6 Correct 83 ms 164472 KB Output is correct
7 Correct 82 ms 164472 KB Output is correct
8 Correct 80 ms 164472 KB Output is correct
9 Correct 81 ms 164472 KB Output is correct
10 Correct 80 ms 164472 KB Output is correct
11 Correct 89 ms 164472 KB Output is correct
12 Correct 86 ms 164600 KB Output is correct
13 Correct 122 ms 164472 KB Output is correct
14 Correct 377 ms 164600 KB Output is correct
15 Correct 511 ms 164472 KB Output is correct
16 Correct 320 ms 164584 KB Output is correct
17 Correct 457 ms 164600 KB Output is correct
18 Correct 249 ms 164472 KB Output is correct
19 Correct 2113 ms 164548 KB Output is correct
20 Correct 2490 ms 164600 KB Output is correct