CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:vulpesomnia
Submission time:2024-11-01 09:42:47 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5details
#20.01 s2, 3, 4, 5details
#3--3, 4, 5details
#4--4, 5details
#5--5details
#6--5details

Code

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

long mod = 1000000000 + 7;

long fc(long factor) { //factorial
  long answer = 1;
  for (long i = 1; i <= factor; i++) {
    answer *= i;
  }
  return answer;
}

long fcm(long factor) { //factorial
  long answer = 1;
  for (long i = 1; i <= factor; i++) {
    answer = (answer % mod * i % mod) % mod;
  }
  return answer;
}

stack<long> createNumberStack(long n) {
  stack<long> answer = {};
  for (long i = 1; i <= n; i++) {
    answer.push(i);
  }
  return answer;
}
vector<long> createNumberLine(long n) {
  vector<long> answer = {};
  for (long i = 1; i <= n; i++) {
    answer.push_back(i);
  }
  return answer;
}

vector<vector<long>> testInput(int amt) {
  vector<vector<long>> answer = {};
  int a = 1;
  int b = 1;
  int n = 1;
  for (int i = 1; i <= amt*amt*amt; i++) {
    if (a % amt == 1 && a != 1) {
      a = 1;
      b++;
      if (b % amt == 1 && b != 1) {
      b = 1;
      n++;
      }
    }
    answer.push_back({n, a, b});
    cout << n << " " << a << " " << b << "\n";
    a++;
  }
  return answer;
}

string printFactor(int n) {
  string answer = "1";
  for (int i = 2 ; i <= n; i++) {
    answer += "*" + to_string(i);
  }
  return answer;
}  

void printArray(vector<long> a) {
  for (int i = 0; i < (int)a.size(); i++) {
    cout << a[i] << " ";
  }
  cout << "\n";
}


long sumOfSums(long d, long n) {
  return (fcm(n)%mod)/((fcm(d)%mod)*(fcm(n-d)%mod));
}

long bruteForce(long n, long a, long b) {
  long d = n-(a+b); //Tasapelit

  long n2 = n-d;
  long p = 0;

  if (a+b <= n && (abs(a-b) != a+b || a+b == 0)) {
    vector<long> l1 = createNumberLine(n2);
    for (long j = 1; j <= fc(n2); j++) {
      long a1 = 0;
      long b1 = 0;
      for (long k = 0; k < (long)l1.size(); k++) {
        if (l1[k] > k+1) {
          b1++;
        } else if (l1[k] < k+1) {
          a1++;
        }
      }
      if (a1 == a && b1 == b) {
        p++;
      }
      next_permutation(l1.begin(),l1.end());
    }
    return (( p % mod ) * ( fcm(n2) % mod ) * ( sumOfSums(d, n) % mod ) * ( sumOfSums(d, n) % mod ) * ( fcm(d) % mod ) ) % mod;
  }
  return 0;
}


long bruteForce2(int n, int a, int b) {
  long p = 0;
  vector<long> l1 = createNumberLine(n);
  vector<long> l2 = createNumberLine(n);
  for (int i = 1; i <= fc(n); i++) {
    for (int j = 1; j <= fc(n); j++) {
      int a1 = 0;
      int b1 = 0;
      for (int k = 0; k < n; k++) {
        if (l1[k] > l2[k]) {
          a1++;
        } else if (l2[k] > l1[k]) {
          b1++;
        }
      }
      if (a1 == a && b1 == b) {
        p++;
      }
      next_permutation(l2.begin(), l2.end());
    }
    next_permutation(l1.begin(), l1.end());
  }
  return p;
}

string isCorrect(long answer, int n, int a, int b) {
  long bf = bruteForce(n, a, b);
  if (answer == bf) {
    return "true " + to_string(bf);
  } else {
    return "false A: " + to_string(answer) + " | BF: " + to_string(bf) + " " + to_string(n) + " " + to_string(a) + " " + to_string(b);
  }
}

long sumOfSums2(long d, long n) {
  return (fc(n))/((fc(d))*(fc(n-d)));
}

//Current iteration = a+b, koska tasapelejä ei lasketa.
long iterateGame(vector<long> nl, long a, long b, long a1, long b1) {
  //printArray(nl);
  long i = a1+b1+1;
  long p = 0;
  int size = (int)nl.size();
  for (int j = 0; j < size; j++) {
    long a2 = 0;
    long b2 = 0;
    long num = nl[j];
    bool work = true;
    if (i > num) {
      a2++;
    } else if (i < num) {
      b2++;
    } else { //Tasapeli, ei mahdollista.
      work = false;
    }
    if (a1+a2 > a || b1+b2 > b) {
      work = false;
      //cout << "False permutation, no more solutions." << " i: " << i << " num: " << num << endl;
    } else if (size == 1 && (a == a1+a2 && b == b1+b2)) {
      //cout << "Permutation found" << " i: " << i << " num: " << num << endl;
      return 1;
      //p += 1;
    }
    //cout << "i: " << i << " a: " << a1 << " b: " << b1 << " num: " << num << "\n";
    if (work) {
      //cout << "Continue." << " i: " << i << " num: " << num << endl;
      vector<long> nnl = nl;
      nnl.erase(nnl.begin() + j);
      p += iterateGame(nnl, a, b, a1+a2, b1+b2);
    }
  }
  return p;
}

int main() {
  int t;
  vector<vector<long>> g = {};
  cin >> t;
  for (int i = 0; i < t; i++) {
    long n, a, b;
    cin >> n >> a >> b;
    g.push_back({n, a, b});
  }

  for (int i = 0; i < (int)g.size(); i++) {
    long n = g[i][0];
    long a = g[i][1];
    long b = g[i][2];
    long d = n-(a+b); //Tasapelit

    long n2 = n-d; //Uusi n
    long p = 0;

    if ((n == 1 || n == 0)&& a+b == 0) {
      cout << 1 << "\n";
      continue;
    }

    if (a+b <= n && (abs(a-b) != a+b || a+b == 0)) {
      vector<long> l1 = createNumberLine(n2);
      p = iterateGame(l1, a, b, 0, 0);
      long vastaus = ((p%mod) * (fcm(n2)%mod) * (sumOfSums(d, n)%mod) * (sumOfSums(d, n)%mod) * (fcm(d)%mod))%mod;
      //cout << isCorrect(vastaus, n, a, b) << "\n";
      cout << vastaus << "\n";

    } else {
      //cout << isCorrect(0, n, a, b) << "\n";
      cout << 0 << "\n";
    }
  }
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict:

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:

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)