Task: | Kortit II |
Sender: | vulpesomnia |
Submission time: | 2024-11-01 09:42:47 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5 | details |
#2 | WRONG ANSWER | 0.01 s | 2, 3, 4, 5 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
#4 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#5 | TIME LIMIT EXCEEDED | -- | 5 | details |
#6 | TIME LIMIT EXCEEDED | -- | 5 | details |
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: WRONG ANSWER
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: WRONG ANSWER
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
1000 2000 1107 508 2000 1372 249 2000 588 65 2000 1739 78 ... |
correct output |
---|
750840601 678722180 744501884 159164549 868115056 ... |
user output |
---|
(empty) |