oj.uz

Submission #716454

# Submission time Handle Problem Language Result Execution time Memory
716454 2023-03-30T06:24:14 Z vjudge1 Beautiful row (IZhO12_beauty) C++17
100 / 100
 894 ms 134704 KB 
// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")  
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll; 
typedef pair<int, int> pii;

const int P = 5;
const int K = 110;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 100;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const string C[] = {"NO\n", "YES\n"};   

int n;
int a[20];
bool is[20][20];
vector<int>g[maxn];
ll dp[20][(1<<20)];
    
bool ok(int x, int y){
    if(__builtin_popcount(x) == __builtin_popcount(y)) return 1;
    int cnt = 0;
    while(x){
        if(x%3 == 1) cnt++;
        x /= 3;
    }
    while(y){
        if(y%3 == 1) cnt--;
        y /= 3;
    }
    return (cnt == 0);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
        for(int j=0; j<i; j++){
            if(ok(a[i], a[j])){
                is[i][j] = is[j][i] = 1;
            }
        }
        dp[i][1<<i] = 1;
    }
    for(int mask=1; mask<(1<<n); mask++){
        vector<int>a, b;
        for(int i=0; i<n; i++){
            if(bit(mask, i)) a.pb(i);
            else b.pb(i);
        }
        for(int i: a){
            for(int to: b){
                if(is[i][to]){
                    dp[to][mask^(1<<to)] += dp[i][mask];
                }
            }
        }
    }
    ll ans = 0;
    for(int i=0; i<n; i++) ans += dp[i][(1<<n)-1];
    cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7396 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 15 ms 8992 KB Output is correct
12 Correct 13 ms 9056 KB Output is correct
13 Correct 46 ms 14344 KB Output is correct
14 Correct 201 ms 37188 KB Output is correct
15 Correct 190 ms 37252 KB Output is correct
16 Correct 220 ms 37104 KB Output is correct
17 Correct 231 ms 37124 KB Output is correct
18 Correct 215 ms 37108 KB Output is correct
19 Correct 889 ms 134704 KB Output is correct
20 Correct 894 ms 134600 KB Output is correct