oj.uz

Submission #1077687

# Submission time Handle Problem Language Result Execution time Memory
1077687 2024-08-27T08:35:50 Z coolboy19521 Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 205392 KB 
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 22;

bool vi[1ll << sz][sz];
ll dp[1ll << sz][sz];
int tw[sz], tr[sz];
int a[sz], n;

bool matc(int i, int j) {
    if (tw[i] == tw[j] || tr[i] == tr[j])
        return true;
    return false;
}

ll go(int i, ll bt) {
    if (bt == (1ll << n) - 1) return 1ll;
    bool& v = vi[bt][i];
    ll& r = dp[bt][i];
    if (v) return r;
    v = true;
    for (int j = 0; j < n; j ++) {
        int f = bt & (1ll << j);
        if (!f && matc(i, j))
            r += go(j, bt | (1 << j));
    }
    return r;
}

void zero() {
    for (int i = 0; i < (1ll << n); i ++)
        for (int j = 0; j < n; j ++)
            dp[i][j] = vi[i][j] = 0;
}

signed main() {
    cin >> n;

    for (int i = 0; i < n; i ++)
        cin >> a[i];

    for (int i = 0; i < n; i ++) {
        for (int cn = a[i]; 0 < cn; cn /= 2)
            tw[i] += cn % 2;
        for (int cn = a[i]; 0 < cn; cn /= 3)
            tr[i] += 1 == cn % 3;
    }

    ll cn = 0;

    for (int i = 0; i < n; i ++) {
        zero();
        cn += go(i, 1ll << i);
    }

    cout << cn << '\n';
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 40 ms 5468 KB Output is correct
12 Correct 25 ms 3420 KB Output is correct
13 Correct 294 ms 13144 KB Output is correct
14 Correct 1962 ms 51216 KB Output is correct
15 Correct 2685 ms 51212 KB Output is correct
16 Correct 1151 ms 51212 KB Output is correct
17 Correct 1668 ms 53080 KB Output is correct
18 Correct 855 ms 53080 KB Output is correct
19 Execution timed out 3049 ms 205392 KB Time limit exceeded
20 Halted 0 ms 0 KB -