CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:PMak
Submission time:2024-11-03 19:35:44 +0200
Language:C++ (C++17)
Status:READY
Result:8
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3, 4, 5details
#2ACCEPTED0.18 s2, 3, 4, 5details
#3--3, 4, 5details
#4--4, 5details
#5--5details
#6--5details

Compiler report

input/code.cpp:22:19: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   22 | void print(vector<auto> v) {
      |                   ^~~~
input/code.cpp:27:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   27 | void println(vector<auto> v) {
      |                     ^~~~
input/code.cpp: In function 'int solve(std::vector<int>, int, int, int)':
input/code.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if (p2.size() == n) {
      |         ~~~~~~~~~~^~~~

Code

#include <bits/stdc++.h>

#define F0R(n) for (int i=0; i<n; i++)
#define FOR(from, to) for (int i = from; i < to; i++)
#define R0F(n) for (int i = n; i>=0; --i)
#define ROF(from, to) for (int i = from; i >= to; --i)

#define ll long long
#define mod (int) (1e9 + 7)
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define pii pair<int, int>
#define pci pair<char, int>
#define pll pair<ll, ll>
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;

void print(vector<auto> v) {
	for (auto it = v.begin(); it != v.end(); ++it)
		cout << *it << " ";
}

void println(vector<auto> v) {
	for (auto it = v.begin(); it != v.end(); ++it)
		cout << *it << " ";
	cout << "\n";
}

vector<vi> adj(int(1e5+1), vi());
vi vis(int(1e5+1));

pii score(vi& p2) {
    int sca=0, scb=0, n = p2.size();
    F0R (n) {
        if (p2[i]<i+1)
            ++sca;
        else if (p2[i]>i+1)
            ++scb;
    }

    return {sca, scb};
}

bool valid(vi& p2, int a, int b) {
    int sca=0, scb=0, n = p2.size();
    F0R (n) {
        if (p2[i]<i+1)
            ++sca;
        else if (p2[i]>i+1)
            ++scb;
        if (sca > a || scb > b)
            return false;
    }

    return (sca == a && scb == b);
}

int solve(vi p2, int n, int a, int b) {
    bool done = valid(p2, a, b);
    auto [sca, scb] = score(p2);

    if (p2.size() == n) {
        if (done) {
            // print(p2);
            return 1;
        }
        else
            return 0;
    }

    if (sca > a || scb > b)
        return 0;

    int ans = 0;
    set<int> st;
    for (int x : p2) st.insert(x);
    F0R (n) {
        if (st.count(i+1)) {
            continue;
        }
        p2.push_back(i+1);
        ans += solve(p2, n, a, b);
        p2.erase(--p2.end());
    }
    return ans;
}

vi fact_mod(2001);
void build() {
    fact_mod[0] = 1;
    FOR (1, 2001)
        (fact_mod[i] = fact_mod[i-1]*i) %= mod;

}

int nCr(int n, int k) {
    if (k <= 0) return 1;
    int ans = 1;
    FOR (1, n+1)
        (ans *= i) %= mod;
    FOR (1, k+1)
        (ans /= i) %= mod;
    FOR (1, n-k+1)
        (ans /= i) %= mod;
    return ans;
}

void soln() {
    int n, a, b;
    cin >> n >> a >> b;

    ll ans = 0, fact_mod = 1;

    F0R (n) {
        (fact_mod *= i+1) %= mod;
    }

    if ((a==0 && b!=0) || (a!=0 && b==0)) {
        cout << "0\n";
        return;
    }

    int new_n = n-a-b;
    if (new_n < 0) {
        cout << "0\n";
        return;
    }

    ans = solve({}, a+b, a, b) % mod;
    (ans *= nCr(n, n-a-b)) %= mod;
    (ans *= fact_mod) %= mod;
    cout << ans << "\n";
    return;

    vi p1_2(new_n);
    vi p2_2(new_n);
    iota(p1_2.begin(), p1_2.end(), a+b+1);
    iota(p2_2.begin(), p2_2.end(), a+b+1);

    n=a+b;
    set<int> st;
    vi p1(n);
    vi p2(n, 0);
    F0R (n) p1[i]=i+1, p2[i] = i+1;

    auto [sca, scb] = score(p2);
    if ((sca == a) && (scb == b)) {
        cout << "YES\n";
        println(p1_2);
        println(p2_2);
        return;
    }

    int p = 0; ++a;++b;
    while (--a>0 && --b>0) {
        swap(p2[p], p2[n-p-1]);
        ++p;
    }
    while (a-->0) {
        swap(p2[p], p2[n-1]);
        ++p;
    }
    b--;
    while (b-->0) {
        swap(p2[p-1], p2[p]);
        ++p;
    }

    cout << "YES\n";
    print(p1); println(p1_2);
    print(p2); println(p2_2);
}

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

    build();
    int tc;
    cin >> tc;
    while (tc--) soln();
    return 0;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
54
4 4 0
3 1 3
3 2 2
4 0 4
...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
284
6 1 0
5 0 2
7 1 5
7 7 5
...

correct output
0
0
35280
0
36720
...

user output
0
0
35280
0
36720
...

Test 3

Group: 3, 4, 5

Verdict:

input
841
19 3 12
19 19 13
19 7 13
20 11 15
...

correct output
40291066
0
0
0
0
...

user output
(empty)

Test 4

Group: 4, 5

Verdict:

input
1000
15 12 6
7 1 6
44 4 26
6 6 5
...

correct output
0
5040
494558320
0
340694548
...

user output
(empty)

Test 5

Group: 5

Verdict:

input
1000
892 638 599
966 429 655
1353 576 1140
1403 381 910
...

correct output
0
0
0
249098285
0
...

user output
(empty)

Test 6

Group: 5

Verdict:

input
1000
2000 1107 508
2000 1372 249
2000 588 65
2000 1739 78
...

correct output
750840601
678722180
744501884
159164549
868115056
...

user output
(empty)