Kortit II

input/code.cpp: In function 'unsigned int solve(int, int, int)':
input/code.cpp:75:25: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   75 |     if (a + b > n || (a == 0 ^ b == 0))
      |                       ~~^~~~

#include <iostream>
#include <set>

using namespace std;

const unsigned int M = 1000000007;

unsigned int nCrize(unsigned int n, unsigned int k, unsigned int opts)
{
    for (unsigned int i = k + 1; i <= n; i++)
    {
        opts = (opts * i) % M;
    }
    for (unsigned int i = n - k + 1; i <= n; i++)
    {
        opts = (opts * i) % M;
    }
    return opts;
}

unsigned int nCr(unsigned int n, unsigned int k)
{
    if (k == 0 || k == n)
    {
        return 1;
    }
    long long result = 1;
    for (unsigned int i = k + 1; i <= n; i++)
    {
        result = (result * i);
    }
    for (unsigned int i = 2; i <= n - k; i++)
    {
        result = result / i;
    }
    return result % M;
}

int options = 0;

// a is smaller at start, playing agst b
void search(int a, int b, int i, set<int> &used)
{
    // cout << a << "," << b << "," << i << "\n";
    // cout << options << "\n";
    // for (const auto el : unused)
    // {
    //     cout << el << ",";
    // }
    // cout << "\n";
    if (a < 0 || b < 0)
    {
        return;
    }
    if (a == 0 && b == 0)
    {

        options = (options + 1) % M;
        return;
    }
    for (int j = 1; j < i + a + b; j++)
    {
        if (j == i || used.find(j) != used.end())
            continue;
        used.insert(j);
        search(a - (j > i), b - (j < i), i + 1, used);
        used.erase(j);
    }
}

unsigned int solve(int n, int a, int b)
{
    options = 0;
    int draws = n - a - b;
    if (a + b > n || (a == 0 ^ b == 0))
    {
        return 0;
    }
    set<int> used;
    search(min(a, b), max(a, b), 1, used);
    // Somenum = combinations where there are a + b cards and a has them in order

    return nCrize(n, draws, options);
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n, a, b;
        cin >> n >> a >> b;
        cout << solve(n, a, b) << "\n";
    }
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED