oj.uz

Submission #1077700

# Submission time Handle Problem Language Result Execution time Memory
1077700 2024-08-27T08:38:55 Z coolboy19521 Beautiful row (IZhO12_beauty) C++17
0 / 100
 2527 ms 262144 KB 
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 22;

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

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;
    int& v = vi[bt][i];
    ll& r = dp[bt][i];
    if (v == pc) return r;
    v = pc, r = 0;
    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;
}

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 ++) {
        pc ++;
        cn += go(i, 1ll << i);
    }

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 49 ms 6116 KB Output is correct
12 Correct 27 ms 6120 KB Output is correct
13 Correct 298 ms 17244 KB Output is correct
14 Correct 1637 ms 68144 KB Output is correct
15 Correct 2527 ms 68148 KB Output is correct
16 Correct 1217 ms 68328 KB Output is correct
17 Correct 2134 ms 68144 KB Output is correct
18 Correct 950 ms 68144 KB Output is correct
19 Runtime error 166 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -