oj.uz

답안 #1077648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077648 2024-08-27T08:29:28 Z coolboy19521 아름다운 순열 (IZhO12_beauty) C++17
0 / 100
 2 ms 2396 KB 
#include "bits/stdc++.h"
#define ll long long
#define int ll

using namespace std;

const int sz = 22;

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

void zero() {
    for (int i = 0; i < (1 << 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;
        //cout << a[i] << ' ' << tw[i] << ' ' << tr[i] << '\n';
    }

    ll cn = 0;

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

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

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 2 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -