Kortit II

input/code.cpp: In function 'long long unsigned int recursive_get_solutions(std::vector<unsigned int>, std::vector<unsigned int>, unsigned int, unsigned int)':
input/code.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i = 0; i < numbers_left.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

// BRUTE FORCE APPROACH
// ONLY FOR GETTING A COUPLE OF POINTS
 
#include <iostream>
#include <stdlib.h>
#include <vector>
 
const inline unsigned int mod_by = 1000000007;
 
unsigned long long factorial(unsigned int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n-1);
}
 
bool is_valid(std::vector<unsigned int> moves, unsigned int p1_wins, unsigned int p2_wins) {
    unsigned int cur_p1_wins = 0;
    unsigned int cur_p2_wins = 0;
    
    for (unsigned int i = 0; i < moves.size(); i++ ) {
        if (moves.at(i) > i) {
            cur_p1_wins++;
        } else if (moves.at(i) < i) {
            cur_p2_wins++;
        }
        if (cur_p1_wins > p1_wins || cur_p2_wins > p2_wins) {
            return false;
        }
    }
    return (cur_p1_wins == p1_wins && cur_p2_wins == p2_wins);
}
 
unsigned long long recursive_get_solutions(std::vector<unsigned int> moves, std::vector<unsigned int> numbers_left, unsigned int p1_wins, unsigned int p2_wins) {
    if (numbers_left.size() == 0) {
        return (is_valid(moves, p1_wins, p2_wins) ? 1 : 0);
    } else {
        unsigned long long solutions = 0;
        for (int i = 0; i < numbers_left.size(); i++) {
            std::vector<unsigned int> moves_copy = std::vector<unsigned int>(moves);
            std::vector<unsigned int> numbers_left_copy = std::vector<unsigned int>(numbers_left);
            moves_copy.push_back(numbers_left.at(i));
            numbers_left_copy[i] = numbers_left_copy.at(numbers_left_copy.size() - 1);
            numbers_left_copy.pop_back();
 
            solutions += recursive_get_solutions(moves_copy, numbers_left_copy, p1_wins, p2_wins);
            solutions = solutions % mod_by;
        }
        return solutions;
    }
}
 
int main() {
    unsigned int row_count;
    std::cin >> row_count;
    
    unsigned int *answers = (unsigned int *) malloc(row_count * sizeof(unsigned int));
 
    for (unsigned int i = 0; i < row_count; i++) {
        unsigned int n, a, b;
        std::cin >> n >> a >> b;
 
        // fix p2 moves to be 1..n
        std::vector<unsigned int> numbers;
        numbers.reserve(n);
        
        for (unsigned int i = 0; i < n; i++) {
            numbers.push_back(i);
        }
 
        unsigned long long solutions = recursive_get_solutions(std::vector<unsigned int> {}, numbers, a, b);
 
        answers[i] = (solutions % mod_by) * (factorial(n) % mod_by);
    }
 
    for (unsigned int i = 0; i < row_count; i++) {
        std::cout << (answers[i] % mod_by) << std::endl;
    }
 
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

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