Kortit II

input/code.cpp: In function 'int dfs(std::vector<int>&, std::set<int>&, std::pair<int, int>&)':
input/code.cpp:27:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if ( (nums.size() == n) && (score == pair<int, int>(0, 0)) )
      |           ~~~~~~~~~~~~^~~~
input/code.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if ( i < nums.size() )
      |              ~~^~~~~~~~~~~~~
input/code.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         else if ( i > nums.size() )
      |                   ~~^~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
 
 
/*
Nykynen suunnitelma:
1. Peli voi kulkea n! eri tavalla, sillä samat kortit pelattuna pareittain eri järjestyksessä johtaa samaan tulokseen
2. Tämän jälkeen katsotaan jokaiselle numerolle, mikä on pienin ja suurin luku millä sen voi korvata
3. Toistetaan askel 2 memoisaatiolla, kunnes ollaan valmiita
*/
 
int n;
int mod = 1e9+7;

struct mem_type {
    size_t length;
    set<int> not_used;
    pair<int, int> score;
};

map<pair<size_t, pair<set<int>, pair<int, int>>>, int> mem;
 
int dfs ( vector<int>& nums, set<int>& not_used, pair<int, int>& score ) {
    if ( (nums.size() == n) && (score == pair<int, int>(0, 0)) )
        return 1;
    else if ( score.first < 0 || score.second < 0 )
        return 0;
    else if ( mem.find({nums.size(), {not_used, score}}) != mem.end() )
        return mem[{nums.size(), {not_used, score}}];

    int ans = 0;
    auto new_not_used = not_used;
    for ( auto i : not_used) {

        nums.push_back(i);
        auto new_score = score;
        new_not_used.erase(i);

        if ( i < nums.size() )
            new_score.second--;
        else if ( i > nums.size() )
            new_score.first--;

        ans += dfs(nums, new_not_used, new_score);
        ans %= mod;

        nums.pop_back();
        new_not_used.insert(i);
    }

    mem[{nums.size(), {not_used, score}}] = ans;
    return ans;
}
 
 
int main () {
    int t;
    cin >> t;
 
    int64_t ans[t];
    
    for ( int i = 0; i < t; i++ ) {
        
        int a, b;
 
        cin >> n >> a >> b;
 
        if ( (a+b) > n || (a == 0 && b != 0) || (a != 0 && b == 0)) {
            ans[i] = 0;
            continue;
        }

        vector<int> nums;
        set<int> not_used;
        
        pair<int, int> score = {a, b};

        for ( int i = 1; i <= n; i++ )
            not_used.insert(i);

        ans[i] = int64_t(dfs(nums, not_used, score));
        
        int64_t mod_long = mod;
        for (int64_t j = 2; j <= n; j++) {
            ans[i] *= j;
            ans[i] %= mod_long;
        }
    }
 
    for (auto n : ans)
        cout << n << "\n";
}

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