Task: | Kortit II |
Sender: | DLPS |
Submission time: | 2024-11-10 23:06:47 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 3 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 3 |
#2 | TIME LIMIT EXCEEDED | 0 |
#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 | TIME LIMIT EXCEEDED | -- | 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: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 masksconstexpr 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: TIME LIMIT EXCEEDED
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: 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) |