CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:DLPS
Submission time:2024-11-10 23:06:47 +0200
Language:C++ (C++20)
Status:READY
Result:3
Feedback
groupverdictscore
#1ACCEPTED3
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#2--2, 3, 4, 5details
#3--3, 4, 5details
#4--4, 5details
#5--5details
#6--5details

Compiler report

input/code.cpp:22:780: warning: integer constant is so large that it is unsigned
   22 | constexpr uint64_t bits[64] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808 };
      |...

Code

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define byte unsigned char
// Yhteisi� yhdelle testille.
int cardCount = 0;
int aTarget = 0;
int bTarget = 0;
int maxZeros = 0;
unordered_map<size_t, int> seenStates;
size_t correctHash = 0;
bool correctHashSet = false;
int CALLS = 0;
// Bit masks
constexpr uint64_t bits[64] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808 };
constexpr uint64_t rbits[64] = { 18446744073709551614, 18446744073709551613, 18446744073709551611, 18446744073709551607, 18446744073709551599, 18446744073709551583, 18446744073709551551, 18446744073709551487, 18446744073709551359, 18446744073709551103, 18446744073709550591, 18446744073709549567, 18446744073709547519, 18446744073709543423, 18446744073709535231, 18446744073709518847, 18446744073709486079, 18446744073709420543, 18446744073709289471, 18446744073709027327, 18446744073708503039, 18446744073707454463, 18446744073705357311, 18446744073701163007, 18446744073692774399, 18446744073675997183, 18446744073642442751, 18446744073575333887, 18446744073441116159, 18446744073172680703, 18446744072635809791, 18446744071562067967, 18446744069414584319, 18446744065119617023, 18446744056529682431, 18446744039349813247, 18446744004990074879, 18446743936270598143, 18446743798831644671, 18446743523953737727, 18446742974197923839, 18446741874686296063, 18446739675663040511, 18446735277616529407, 18446726481523507199, 18446708889337462783, 18446673704965373951, 18446603336221196287, 18446462598732840959, 18446181123756130303, 18445618173802708991, 18444492273895866367, 18442240474082181119, 18437736874454810623, 18428729675200069631, 18410715276690587647, 18374686479671623679, 18302628885633695743, 18158513697557839871, 17870283321406128127, 17293822569102704639, 16140901064495857663, 13835058055282163711, 9223372036854775807 };
const uint64_t FNVp = 1099511628211ULL;
const uint64_t FNVoffset = 14695981039346656037ULL;
static void InsertHand(int card, uint64_t* hand)
{
int index = card / 64;
int bit = card % 64;
hand[index] |= bits[bit];
}
void HandToCards(uint64_t* hand, int count, int ret[2000])
{
int added = 0;
for (int index = 0; index < ceil(cardCount / 64.f); index++)
{
for (int bit = 0; bit < 64; bit++)
{
if ((hand[index] & bits[bit]) > 0)
{
ret[added] = index * 64 + bit;
++added;
if (added == count)
{
return;
}
}
}
}
return;
}
static void RemoveCard(int card, uint64_t* hand)
{
hand[(card) / 64] &= rbits[(card) % 64];
}
static void HandToString(uint64_t* hand, string& target)
{
for (int i = 0; i < 32; ++i)
{
target += hand[i];
}
}
static void HashHand(uint64_t* hand, size_t& target)
{
/*
std::hash<uint64_t> hasher;
for (int i = 0; i < ceil(cardCount / 64.f); ++i)
{
target ^= hasher(hand[i]) + 0x9e3779b9 + (target << 6) + (target >> 2);
}*/
for (int i = 0; i < ceil(cardCount / 64.f); ++i)
{
target ^= hand[i];
target *= FNVp;
}
}
size_t HashState(uint64_t* aHand, uint64_t* bHand, int& aScore, int& bScore, int& ties)
{
std::hash<int> hasher;
size_t hash = FNVoffset;
HashHand(aHand, hash);
HashHand(bHand, hash);
//hash ^= hasher(aScore) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
//hash ^= hasher(bScore) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
hash ^= aScore;
hash *= FNVp;
hash ^= bScore;
hash *= FNVp;
return hash;
}
size_t HashTargets()
{
uint64_t preHash = cardCount * 100000000 + aTarget * 10000 + bTarget;
std::hash<uint64_t> hasher;
return hasher(preHash);
}
void AddHash(size_t& hash, int& value)
{
if (correctHashSet && hash == correctHash)
{
return;
}
//seenStates.insert({hash, value});
//seenStates.emplace(hash, value);
seenStates[hash] = value;
}
static int TestBranch(uint64_t* aHand, uint64_t* bHand, int aScore, int bScore, int ties)
{
CALLS++;
int remCards = cardCount - aScore - bScore - ties;
if (!(remCards > 0))
{
if (aScore == aTarget && bScore == bTarget && ties == maxZeros)
{
if (!correctHashSet)
{
correctHash = HashState(aHand, bHand, aScore, bScore, ties);
correctHashSet = true;
seenStates.erase(correctHash);
}
return 1;
}
else
{
return 0;
}
}
if (aScore > aTarget || bScore > bTarget || ties > maxZeros)
{
return 0;
}
int aCards[2000];
HandToCards(aHand, remCards, aCards);
int bCards[2000];
HandToCards(bHand, remCards, bCards);
int childTotal = 0;
for (int i = 0; i < remCards; i++)
{
int removedACard = aCards[i];
RemoveCard(removedACard, aHand);
for (int j = 0; j < remCards; j++)
{
int removedBCard = bCards[j];
RemoveCard(removedBCard, bHand);
int newScoreA = aScore;
int newScoreB = bScore;
int newTies = ties;
if (removedACard == removedBCard)
{
newTies++;
}
else if (removedACard > removedBCard)
{
newScoreA++;
}
else
{
newScoreB++;
}
size_t hash = HashState(aHand, bHand, newScoreA, newScoreB, newTies);
if (seenStates.contains(hash))
{
childTotal += seenStates[hash];
}
else
{
int ret = TestBranch(aHand, bHand, newScoreA, newScoreB, newTies);
AddHash(hash, ret);
childTotal += ret;
}
childTotal %= 1000000007;
InsertHand(removedBCard, bHand);
}
InsertHand(removedACard, aHand);
}
return childTotal % 1000000007;
}
static void Test(int n, int a, int b)
{
if (a + b > n)
{
cout << "0";
return;
}
cardCount = n;
aTarget = a;
bTarget = b;
maxZeros = n - a - b;
seenStates.clear();
uint64_t baseHandA[32] = { 0 };
uint64_t baseHandB[32] = { 0 };
for (int i = 0; i < n; i++)
{
InsertHand(i + 1, baseHandA);
InsertHand(i + 1, baseHandB);
}
cout << TestBranch(baseHandA, baseHandB, 0, 0, 0);
}
int main()
{
int testCount = 0;
cin >> testCount;
cout << "";
for (int i = 0; i < testCount; i++)
{
int n, a, b;
cin >> n >> a >> b;
Test(n, a, b);
if (i < testCount - 1)
{
cout << "\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:

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

correct output
0
0
35280
0
36720
...

user output
(empty)

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)