Submission #1090992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090992		Phuoc	Beautiful row (IZhO12_beauty)	C++14	100 / 100	665 ms	181036 KiB

beauty

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define el '\n'
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define fi first
#define se second


template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b){a = b; return true;} return false;
    }

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }

const int MOD = 1337377;

template <class T1, class T2>
    void add(T1 &a, T2 b) {
        a += b;
        if(a >= MOD) a -= MOD;
    }

const ll INF = (ll)1e18 + 10LL;
const int oo = (int)1e9 + 10;
const int MAX = 250250;
const int LG = 18;

int N, A[MAX], two[MAX], three[MAX];

void init (void) {
    cin >> N;
    FOR(i, 1, N) {
        cin >> A[i];
        two[i] = __builtin_popcount(A[i]);
        int x = A[i];
        while(x > 0) {
            if(x % 3 == 1) three[i]++;
            x /= 3;
        }
    }
}

ll f[MASK(21) + 10][22];

void solve (void) {
    FOR(i, 0, N) f[MASK(i)][i] = 1;
    FOR(mask, 0, MASK(N) - 1) {
        for(int i = 0; i < N; i++) if(BIT(mask, i)) {
            for(int j = 0; j < N; j++) if(!BIT(mask, j)) {
                if(two[i + 1] == two[j + 1] || three[i + 1] == three[j + 1]) {
                    f[mask | MASK(j)][j] += f[mask][i];
                }
            }
        }
    }
    ll ans = 0;
    FOR(i, 0, N - 1) {
        ans += f[MASK(N) - 1][i];
    }
    cout << ans << el;
}

int main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    int ntest = 1;
    // cin >> ntest;
    // srand(time(0));
    while(ntest--) {
        init();
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100