Task: | Kortit II |
Sender: | DLPS |
Submission time: | 2024-10-31 21:10:05 +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.01 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:18:776: warning: integer constant is so large that it is unsigned 18 | const 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
#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; // Bit masks const 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 }; const 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 smasks[64] = { 18446744073709551615, 18446744073709551614, 18446744073709551612, 18446744073709551608, 18446744073709551600, 18446744073709551584, 18446744073709551552, 18446744073709551488, 18446744073709551360, 18446744073709551104, 18446744073709550592, 18446744073709549568, 18446744073709547520, 18446744073709543424, 18446744073709535232, 18446744073709518848, 18446744073709486080, 18446744073709420544, 18446744073709289472, 18446744073709027328, 18446744073708503040, 18446744073707454464, 18446744073705357312, 18446744073701163008, 18446744073692774400, 18446744073675997184, 18446744073642442752, 18446744073575333888, 18446744073441116160, 18446744073172680704, 18446744072635809792, 18446744071562067968, 18446744069414584320, 18446744065119617024, 18446744056529682432, 18446744039349813248, 18446744004990074880, 18446743936270598144, 18446743798831644672, 18446743523953737728, 18446742974197923840, 18446741874686296064, 18446739675663040512, 18446735277616529408, 18446726481523507200, 18446708889337462784, 18446673704965373952, 18446603336221196288, 18446462598732840960, 18446181123756130304, 18445618173802708992, 18444492273895866368, 18442240474082181120, 18437736874454810624, 18428729675200069632, 18410715276690587648, 18374686479671623680, 18302628885633695744, 18158513697557839872, 17870283321406128128, 17293822569102704640, 16140901064495857664, 13835058055282163712, 9223372036854775808 }; //const uint64_t emasks[64] = { 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247, 4503599627370495, 9007199254740991, 18014398509481983, 36028797018963967, 72057594037927935, 144115188075855871, 288230376151711743, 576460752303423487, 1152921504606846975, 2305843009213693951, 4611686018427387903, 9223372036854775807, 18446744073709551615 }; static void InsertHand(int card, vector<uint64_t>& hand) { byte index = card / 64; byte bit = card % 64; hand[index] |= bits[bit]; } static vector<int> HandToCards(vector<uint64_t>& hand) { vector<int> ret; ret.reserve(cardCount); for (int index = 0; index < hand.size(); index++) { for (int bit = 0; bit < 64; bit++) { if ((hand[index] & bits[bit]) > 0) { ret.push_back(index * 64 + bit); } } } return ret; } static void RemoveCard(int card, vector<uint64_t>& hand) { hand[(card) / 64] &= rbits[(card) % 64]; } static void HandToString(vector<uint64_t>& hand, string& target) { for (auto& num : hand) { target += to_string(num); } } size_t HashState(vector<uint64_t>& aHand, vector<uint64_t>& bHand, int& aScore, int& bScore, int& ties) { string preHash = ""; preHash.reserve((cardCount / 64 + 1) * 20 + 12); HandToString(aHand, preHash); HandToString(bHand, preHash); preHash += to_string(aScore * 10000 + bScore); preHash += to_string(ties); std::hash<string> hasher; return hasher(preHash); } 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(pair<size_t, int>(hash, value)); } static int TestBranch(vector<uint64_t> aHand, vector<uint64_t> bHand, int aScore, int bScore, int ties) { if (aScore > aTarget || bScore > bTarget || ties > maxZeros) { return 0; } if (aScore == aTarget && bScore == bTarget && ties == maxZeros) { if (!correctHashSet) { correctHash = HashState(aHand, bHand, aScore, bScore, ties); correctHashSet = true; seenStates.erase(correctHash); } return 1; } vector<int> aCards = HandToCards(aHand); vector<int> bCards = HandToCards(bHand); int remCards = cardCount - aScore - bScore - ties; int childTotal = 0; for (int i = 0; i < remCards; i++) { vector<uint64_t> newAHand = aHand; RemoveCard(aCards[i], newAHand); for (int j = 0; j < remCards; j++) { vector<uint64_t> newBHand = bHand; RemoveCard(bCards[j], newBHand); int newScoreA = aScore; int newScoreB = bScore; int newTies = ties; if (aCards[i] == bCards[j]) { newTies++; } else if (aCards[i] > bCards[j]) { newScoreA++; } else { newScoreB++; } size_t hash = HashState(newAHand, newBHand, newScoreA, newScoreB, newTies); if (seenStates.contains(hash)) { childTotal += seenStates[hash]; } else { int ret = TestBranch(newAHand, move(newBHand), newScoreA, newScoreB, newTies); AddHash(hash, ret); childTotal += ret; } childTotal %= 1000000007; } } return childTotal % 1000000007; } static void Test(int n, int a, int b) { if (a + b > n) { cout << "0\n"; return; } cardCount = n; aTarget = a; bTarget = b; maxZeros = n - a - b; seenStates.clear(); vector<uint64_t> baseHand = vector<uint64_t>(n, 0); for (int i = 0; i < n; i++) { InsertHand(i + 1, baseHand); } cout << TestBranch(baseHand, baseHand, 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 ... |
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) |