IEEE-Xtreme-18.0/halving.cpp at main · geethdev/IEEE-Xtreme-18.0 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

const int MODULO = 998244353;

int numPairs;
vector<int> cardColors, rules, boundaries;
map<pair<int, vector<int>>, int> memoization;

int findArrangements(int position, vector<int>& availableNumbers) {
    if (position == numPairs) return 1;

    pair<int, vector<int>> state = {position, availableNumbers};
    if (memoization.count(state)) return memoization[state];

    int arrangements = 0;
    int cardIndex = 2 * position;

    vector<int> firstCardOptions;
    if (cardColors[cardIndex] != -1) firstCardOptions = {cardColors[cardIndex]};
    else firstCardOptions = availableNumbers;

    for (int firstCard : firstCardOptions) {
        if (cardColors[cardIndex] != -1 && cardColors[cardIndex] != firstCard) continue;

        vector<int> secondCardOptions;
        if (cardColors[cardIndex + 1] != -1) secondCardOptions = {cardColors[cardIndex + 1]};
        else {
            secondCardOptions = availableNumbers;
            if (find(secondCardOptions.begin(), secondCardOptions.end(), firstCard) != secondCardOptions.end())
                secondCardOptions.erase(find(secondCardOptions.begin(), secondCardOptions.end(), firstCard));
        }

        for (int secondCard : secondCardOptions) {
            if (cardColors[cardIndex + 1] != -1 && cardColors[cardIndex + 1] != secondCard) continue;
            if (firstCard == secondCard) continue;

            int smallerCard = min(firstCard, secondCard);
            int largerCard = max(firstCard, secondCard);

            if ((rules[position] == 0 && boundaries[position] == smallerCard) ||
                (rules[position] == 1 && boundaries[position] == largerCard)) {

                vector<int> updatedAvailableNumbers = availableNumbers;
                if (cardColors[cardIndex] == -1)
                    updatedAvailableNumbers.erase(find(updatedAvailableNumbers.begin(), updatedAvailableNumbers.end(), firstCard));
                if (cardColors[cardIndex + 1] == -1)
                    updatedAvailableNumbers.erase(find(updatedAvailableNumbers.begin(), updatedAvailableNumbers.end(), secondCard));

                arrangements = (arrangements + findArrangements(position + 1, updatedAvailableNumbers)) % MODULO;
            }
        }
    }

    return memoization[state] = arrangements;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> numPairs;
    cardColors.resize(2 * numPairs);
    rules.resize(numPairs);
    boundaries.resize(numPairs);

    vector<int> availableNumbers;
    vector<bool> isUsed(2 * numPairs + 1, false);

    for (int i = 0; i < 2 * numPairs; i++) {
        cin >> cardColors[i];
        if (cardColors[i] != -1) isUsed[cardColors[i]] = true;
    }

    for (int i = 1; i <= 2 * numPairs; i++) {
        if (!isUsed[i]) availableNumbers.push_back(i);
    }

    for (int i = 0; i < numPairs; i++) cin >> rules[i];
    for (int i = 0; i < numPairs; i++) cin >> boundaries[i];

    cout << findArrangements(0, availableNumbers) << endl;

    return 0;
}