— Dark mode

Datatähti 2025 alku

Kortit II

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
  • Contest has ended
CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:nikke5
Submission time:2024-11-01 23:33:53 +0200
Language:C++ (C++11)
Status:READY
Result:8
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#2ACCEPTED0.01 s2, 3, 4, 5details
#3--3, 4, 5details
#4--4, 5details
#5--5details
#6--5details

Compiler report

input/code.cpp: In function 'void haku(int, int, int)':
input/code.cpp:48:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |     if (v.size() == n)
      |         ~~~~~~~~~^~~~
input/code.cpp:117:13: warning: label 'EHDOT' defined but not used [-Wunused-label]
  117 |             EHDOT :
      |             ^~~~~

Code

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
 
typedef long long ll;
using namespace std;
 
ll n, a, b;
 
ll vastaus;
 
ll kertoma(int x){
    for(int i = x-1; i>0; i--){
        x *= i;
    }
 
    return x;
}
 
int binomialC(int n, int k)
{
    int ans = 1;
    if (k > n - k)
        k = n - k;
 
    for (int i = 0; i < k; i++)
    {
        ans = ans * (n - i);
        ans = ans / (i + 1);
    }
    return ans;
}
 
vector<int> v;
ll p[2001];
 
ll iterations;
 
int winCards;
int losePossibilities;
ll winAddDelayed[2001];
 
void haku(int level, int winsA, int winsB)
{
    if (v.size() == n)
    {
 
        // if (level < v[level-1]){ // JOS B VOITTAA, MERKKAA YLÖS
        //     winsB++;
        // }
        // if (level > v[level-1]){ // JOS A VOITTAA, MERKKAA YLÖS
        //     winsA++;
        // } 
 
    //     ll aTemp = 0;
    //     ll bTemp = 0;
 
    //    for(int i = 0; i<n; i++){
    //         if (v[i] > i+1){
    //             aTemp++;
    //         }
    //         else if (v[i] < i+1){
    //             bTemp++;
    //         }
    //    }
 
        // if (aTemp == a && bTemp == b){
        //     vastaus++;
        // }
 
        if (winsA == a && winsB == b){
            vastaus++;
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
 
            iterations++;
 
            if (p[i]){
                continue;
            }
 
 
            // if (i != n && level > 0)
            // {
            //     losePossibilities -= 1;
 
            //     cout << "LOSE --   " << "winsB: " << winsB << " losePossibilities: " << losePossibilities << " Iteration: " << iterations << " Level: " << level << "\n";
 
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << i2 + 1 << " ";
            //     }
            //     cout << "\n";
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << v[i2] << " ";
            //     }
            //     cout << "\n \n";
            // }
 
            if (level < i)
            { // JOS B VOITTAA, MERKKAA YLÖS
                winsB++;
            }
            if (level > i)
            { // JOS A VOITTAA, MERKKAA YLÖS
                winsA++;
            }
 
            EHDOT :
            if (level == i) {  // JOS TASAPELI, CONTINUE
                continue;
            }
            if (winsB > b){ // JOS B:LLÄ ON ENEMMÄN VOITTOJA KUIN SAISI, CONTINUE
                continue;
            }
            if (winsA > a){ // JOS A:LLA ON ENEMMÄN VOITTOJA KUIN SAISI, CONTINUE
                continue;
            }
 
 
 
 
            // if (v.size() > 0)
            // {
 
                 
 
            //     if (winAddDelayed[level] == 1)
            //     {
            //         winCards++;
            //         winAddDelayed[level] = 2;
            //     }
 
                
 
            //     if (i > level + 1)
            //     {
            //         winCards -= 2;
            //         winAddDelayed[i-1] = 1;
            //     }
            //     else
            //     {
            //         winCards--;
            //     }
 
 
            // }
 
            // if (max(winCards,0) < b-winsB){
 
            //     // CONTINUING  THING STARTS
 
            //     if (v.size() > 0)
            //     {
            //         if (level < i) // JOS B VOITTI, OTA POIS
            //         {
            //             winsB--;
            //         }
            //         if (level > i) // JOS A VOITTI, OTA POIS
            //         {
            //             winsA--;
            //         }
 
            //         if (i > level + 1)
            //         {
            //             winCards += 2;
            //             winAddDelayed[i - 1] = 0;
            //         }
            //         else
            //         {
            //             winCards++;
            //         }
 
            //         if (winAddDelayed[level] == 2)
            //         {
            //             winCards--;
            //             winAddDelayed[level] = 1;
            //         }
 
            //         if (v[level - 1] != n)
            //         {
            //             losePossibilities += 1;
            //         }
            //     }
 
            //     continue;
 
            //     // CONTINUING THING ENDS
            // }
 
            // if (losePossibilities < n-b-(level-winsB)){ // JOS HÄVIÖIDEN MAHDOLLINEN MÄÄRÄ ON VÄHEMMÄN KUIN TARVITTAVA MÄÄRÄ - JO TULLEIDEN HÄVIÖIDEN MÄÄRÄ (jo tulleet erät - voitot)
                
            //     if (i != n){
            //         losePossibilities += 1;
            //     }
 
            //     cout << "CONTINUE  " << "winsB: "<< winsB << " losePossibilities: " << losePossibilities << " Iteration: " << iterations << " Level: " << level << "\n"; 
 
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << i2+1 << " ";
            //     }
            //     cout << "\n";
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << v[i2] << " ";
            //     }
            //     cout << "\n \n";
 
            //     // continue;
            // }
 
            p[i] = 1;
            v.push_back(i);
            haku(level + 1, winsA, winsB);
 
 
 
            p[i] = 0;
            v.pop_back();
 
            if (level < v[level - 1]) // JOS B VOITTI, OTA POIS
            {
                winsB--;
            }
            if (level > v[level - 1]) // JOS A VOITTI, OTA POIS
            {
                winsA--;
            }
 
            // if (v[level - 1] > level + 1)
            // {
            //     winCards += 2;
            //     winAddDelayed[(v[level - 1]) - 1] = 0;
            // }
            // else
            // {
            //     winCards++;
            // }
 
            // if (winAddDelayed[level] == 2)
            // {
            //     winCards--;
            //     winAddDelayed[level] = 1;
            // }
 
            // if (v[level - 1] != n)
            // {
            //     losePossibilities += 1;
 
            //     cout << "ADD ++   " << "i: " << i << " v[level-1]: " << v[level - 1] << " losePossibilities: " << losePossibilities << " Iteration: " << iterations << " Level: " << level << "\n";
 
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << i2 + 1 << " ";
            //     }
            //     cout << "\n";
            //     for (int i2 = 0; i2 < v.size(); i2++)
            //     {
            //         cout << v[i2] << " ";
            //     }
            //     cout << "\n \n";
            // }
        }
    }
}
 
int main() {
 
    int t;
 
    cin >> t;
 
    vector<int> nA;
    vector<int> aA;
    vector<int> bA;
 
    for (int i = 0; i<t; i++){
        cin >> n >> a >> b;
 
        nA.push_back(n);
        aA.push_back(a);
        bA.push_back(b);
 
    }
 
 
    for (int i = 0; i<t; i++){
 
        n = nA[i];
        a = aA[i];
        b = bA[i];
 
 
        if (a != 0 && b != 0){
            if (a+b > n){
                cout << "0" << "\n";
                continue;
            }
        }
        else if (a+b != 0){
            cout << "0" << "\n";
            continue;
        }
 
 
 
 
 
        vastaus = 0;
 
 
        // if (a == 0 && b == 0){
        //     vastaus = kertoma(n);
        //     cout << vastaus << "\n";
        // }
        // else if (a == 1 || b == 1){
        //     vastaus = binomialC(n, n-a-b) * kertoma(n);
        //     cout << vastaus << "\n";
        // }
 
 
        ll Tasapelivaihtoehdot = binomialC(n, n-a-b);
 
        winCards = n-1;
        losePossibilities = n-1;
 
        // POISTAA TASAPELIT
        n = a+b;
 
        haku(1, 0, 0);
 
        n = nA[i];
 
        vastaus *= Tasapelivaihtoehdot;
        // cout << " " << a << " " << b << " " << n << "\n"; 
 
 
        for(int i = 1; i<=n; i++){ // VASTAUS * KERTOMA (n)
            vastaus = (vastaus * i) % 1000000007;
        }
 
        // cout << vastaus << "\n ITERATIONS: " << iterations << "\n";
 
        cout << vastaus << "\n";
 
 
 
    }
 
 
}

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
...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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

correct output
0
0
35280
0
36720
...
view save

user output
0
0
35280
0
36720
...
view save

Test 3

Group: 3, 4, 5

Verdict:

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

correct output
40291066
0
0
0
0
...
view save

user output
(empty)

Test 4

Group: 4, 5

Verdict:

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

correct output
0
5040
494558320
0
340694548
...
view save

user output
(empty)

Test 5

Group: 5

Verdict:

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

correct output
0
0
0
249098285
0
...
view save

user output
(empty)

Test 6

Group: 5

Verdict:

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

correct output
750840601
678722180
744501884
159164549
868115056
...
view save

user output
(empty)

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (nikke5)

2024-11-02 00:04:58 82024-11-02 00:04:35 02024-11-01 23:33:53 82024-11-01 23:33:13 02024-11-01 17:18:26 82024-11-01 17:15:38 02024-11-01 16:17:35 82024-10-31 19:53:15 82024-10-31 16:20:07 82024-10-31 16:18:10 02024-10-30 22:00:37 3