oj.uz

Submission #1090992

# Submission time Handle Problem Language Result Execution time Memory
1090992 2024-09-19T11:43:23 Z Phuoc Beautiful row (IZhO12_beauty) C++14
100 / 100
 665 ms 181036 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 8 ms 3160 KB Output is correct
12 Correct 6 ms 3256 KB Output is correct
13 Correct 29 ms 11608 KB Output is correct
14 Correct 145 ms 45396 KB Output is correct
15 Correct 127 ms 45396 KB Output is correct
16 Correct 146 ms 45392 KB Output is correct
17 Correct 153 ms 45580 KB Output is correct
18 Correct 147 ms 45444 KB Output is correct
19 Correct 665 ms 180820 KB Output is correct
20 Correct 637 ms 181036 KB Output is correct