| Task: | Kortit II |
| Sender: | nikke5 |
| Submission time: | 2024-11-02 00:04:58 +0200 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | 8 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 3 |
| #2 | ACCEPTED | 5 |
| #3 | TIME LIMIT EXCEEDED | 0 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5 | details |
| #2 | ACCEPTED | 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 |
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)
| ~~~~~~~~~^~~~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)
{
// 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 (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 (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 (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;
}
continue;
// CONTINUING THING ENDS
}
if (i != n)
{
losePossibilities -= 1;
}
// 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;
// }
// 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;
// }
// continue;
// }
p[i] = 1;
v.push_back(i);
haku(level + 1, winsA, winsB);
p[i] = 0;
v.pop_back();
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 (i != n)
{
losePossibilities += 1;
}
}
}
}
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];
if (a < b){
a = aA[i];
b = bA[i];
}
else{
b = aA[i];
a = bA[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;
iterations = 0;
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 ... |
| 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: 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) |