Task: | Niitty |
Sender: | Pikaksi |
Submission time: | 2024-11-09 18:09:44 +0200 |
Language: | C++ (C++20) |
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 |
#6 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.18 s | 1, 2, 3, 4, 5, 6 | details |
#2 | ACCEPTED | 0.18 s | 1, 2, 3, 4, 5, 6 | details |
#3 | ACCEPTED | 0.18 s | 1, 2, 3, 4, 5, 6 | details |
#4 | WRONG ANSWER | 0.18 s | 1, 2, 3, 4, 5, 6 | details |
#5 | ACCEPTED | 0.18 s | 1, 2, 3, 4, 5, 6 | details |
#6 | WRONG ANSWER | 0.18 s | 2, 3, 4, 5, 6 | details |
#7 | WRONG ANSWER | 0.18 s | 2, 3, 4, 5, 6 | details |
#8 | ACCEPTED | 0.19 s | 2, 3, 4, 5, 6 | details |
#9 | WRONG ANSWER | 0.19 s | 2, 3, 4, 5, 6 | details |
#10 | WRONG ANSWER | 0.18 s | 3, 4, 5, 6 | details |
#11 | WRONG ANSWER | 0.18 s | 3, 4, 5, 6 | details |
#12 | ACCEPTED | 0.18 s | 3, 4, 5, 6 | details |
#13 | WRONG ANSWER | 0.19 s | 3, 4, 5, 6 | details |
#14 | WRONG ANSWER | 0.19 s | 4, 5, 6 | details |
#15 | WRONG ANSWER | 0.19 s | 4, 5, 6 | details |
#16 | ACCEPTED | 0.19 s | 4, 5, 6 | details |
#17 | WRONG ANSWER | 0.19 s | 4, 5, 6 | details |
#18 | WRONG ANSWER | 0.20 s | 5, 6 | details |
#19 | WRONG ANSWER | 0.24 s | 5, 6 | details |
#20 | ACCEPTED | 0.20 s | 5, 6 | details |
#21 | WRONG ANSWER | 0.22 s | 5, 6 | details |
#22 | WRONG ANSWER | 0.46 s | 6 | details |
#23 | WRONG ANSWER | 0.93 s | 6 | details |
#24 | ACCEPTED | 0.43 s | 6 | details |
#25 | WRONG ANSWER | 0.95 s | 6 | details |
Compiler report
input/code.cpp: In function 'void printRows(int, unsigned int*)': input/code.cpp:13:13: warning: variable 'prewOrTowerSpace' set but not used [-Wunused-but-set-variable] 13 | int prewOrTowerSpace = rowSpace; | ^~~~~~~~~~~~~~~~ input/code.cpp: In function 'long long unsigned int calculateAnsBitMasks(unsigned int, unsigned int*, unsigned int)': input/code.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'const unsigned int' [-Wsign-compare] 42 | for (int y = 0; y < n; y++) { | ~~^~~ input/code.cpp:68:40: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'const int' [-Wsign-compare] 68 | for (unsigned int len = 0; len < nTriangleSize; len++) { // loop orTower bitmasks | ~~~~^~~~~~~~~~~~~~~ input/code.cpp:72:53: warning: comparison of integer expressions of different signedness: 'int' and 'const unsign...
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const unsigned int FIELD_SIZE = 500; const unsigned int FIELD_ROW_OFFSET = FIELD_SIZE * (FIELD_SIZE + 1) / 2; void printRows(int n, unsigned int* field) { for (int y = 0; y < n; y++) { int rowSpace = y * FIELD_ROW_OFFSET; int prewOrTowerSpace = rowSpace; int offsetTriangle = 0; cout << "row:\n"; for (int x = 0; x < n; x++) { int orTowerSpace = rowSpace + offsetTriangle; for (int len = 0; len < n - x; len++) { cout << field[orTowerSpace + len] << " at " << (orTowerSpace + len) << " "; } prewOrTowerSpace = orTowerSpace; offsetTriangle += n - x; cout << "\n"; } } } unsigned long long calculateAnsBitMasks(const unsigned int n, unsigned int* const field, const unsigned int containedFlowers) { unsigned long long ans = 0; const int nTriangleSize = n * (n + 1) / 2; if (__builtin_popcount(containedFlowers) == 1) { ans += n * n; } for (int y = 0; y < n; y++) { unsigned int rowSpace = y * FIELD_ROW_OFFSET; unsigned int prewOrTowerSpace = rowSpace; unsigned int offsetTriangle = n; for (unsigned int x = 1; x < n; x++) { // loop or tower spaces unsigned int orTowerSpace = rowSpace + offsetTriangle; for (unsigned int len = 0; len < n - x; len++) { // loop over or tower unsigned int bitMaskCombination = field[prewOrTowerSpace + len] | field[prewOrTowerSpace + len + 1]; field[orTowerSpace + len] = bitMaskCombination; ans += bitMaskCombination == containedFlowers; } prewOrTowerSpace = orTowerSpace; offsetTriangle += n - x; } } //printRows(n, field); for (unsigned int y = 0; y < n - 1; y++) { // loop rows unsigned int rowSpace = y * FIELD_ROW_OFFSET; for (unsigned int len = 0; len < nTriangleSize; len++) { // loop orTower bitmasks unsigned int bitmaskTriangles = field[rowSpace + len]; for (int orRowIndex = y + 1; orRowIndex < n; orRowIndex++) { // loop other rows to add to main row unsigned int addRowSpace = orRowIndex * FIELD_ROW_OFFSET; //cout << "started or triangle\n"; //cout << "main or tower = " << (mainOrTowerSpace + len) << " add or tower " << (addOrTowerSpace + len) << "\n"; //__builtin_prefetch(field + addRowSpace + FIELD_ROW_OFFSET + len); bitmaskTriangles |= field[addRowSpace + len]; ans += bitmaskTriangles == containedFlowers; } } } return ans; } unsigned long long calculateAnsBitMasks2(const unsigned int n, unsigned int* const field, const unsigned int containedFlowers) { unsigned long long ans = 0; if (__builtin_popcount(containedFlowers) == 1) { ans += n * n; } for (int y = 0; y < n; y++) { unsigned int rowSpace = y * FIELD_ROW_OFFSET; unsigned int prewOrTowerSpace = rowSpace; unsigned int offsetTriangle = n; for (unsigned int x = 1; x < n; x++) { // loop or tower spaces unsigned int orTowerSpace = rowSpace + offsetTriangle; for (unsigned int len = 0; len < n - x; len++) { // loop over or tower unsigned int bitMaskCombination = field[prewOrTowerSpace + len] | field[prewOrTowerSpace + len + 1]; field[orTowerSpace + len] = bitMaskCombination; ans += bitMaskCombination == containedFlowers; } prewOrTowerSpace = orTowerSpace; offsetTriangle += n - x; } } //printRows(n, field);cout << "\n"; for (unsigned int y = 0; y < n - 1; y++) { // loop rows unsigned int rowSpace = y * FIELD_ROW_OFFSET; for (int orRowIndex = y + 1; orRowIndex < n; orRowIndex++) { // loop other rows to add to main row int triangleTraverser = 0; int currentOrTower = 0; int currentOrTowerIndex = 0; //cout << "\nstarting triangle y = " << y << " add row = " << orRowIndex << "\n"; while (true) { //cout << "triangle traverser = " << triangleTraverser << " current orTower = " << currentOrTower << " index in orTower = " << currentOrTowerIndex << "\n"; field[rowSpace + triangleTraverser] |= field[orRowIndex * FIELD_ROW_OFFSET + triangleTraverser]; int flowers = field[rowSpace + triangleTraverser]; if (flowers == containedFlowers) { ans += n - currentOrTower - currentOrTowerIndex; if (currentOrTower == 0) { //cout << "valid at tower = 0\n"; if (triangleTraverser == n - 1) { break; } currentOrTowerIndex += 1; triangleTraverser += 1; } else { //cout << "valid at tower >= 1\n"; triangleTraverser -= n - currentOrTower; currentOrTower -= 1; currentOrTowerIndex += 1; } } else { //cout << "not valid\n"; if (currentOrTowerIndex == n - currentOrTower - 1) { break; } triangleTraverser += n - currentOrTower; currentOrTower += 1; } } } } return ans; } void shuffle(int n, vector<string>& testField) { testField = vector<string>(n); for (int i = 0; i < n; i++) { string row = ""; for (int k = 0; k < n; k++) { row += rand() % 1 + 'A'; } //cout << "row = " << row << "\n"; testField[i] = row; } } int main() { //vector<string> testField = {"AAAAA", "AAAAA", "AABAA", "AAACA", "AAADA"}; //vector<string> testField = {"BAA", "AAB", "AAA"}; //vector<string> testField = {"Z"}; //vector<string> testField = {"AA", "AA"}; //vector<string> testField = {"AAAC", "ABAA", "ABAA", "AAAA"}; //vector<string> testField = {"AAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAA"}; //vector<string> testField = {"ZAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAK"}; //vector<string> testField = {"AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA","AAAAAAAAAA",}; //vector<string> testField = {"AUFCHGK","GXAPVWB","NUHYMEA","HSCSNSI","IMBMTJS","TPVRJUF","SIKDVWY"}; //vector<string> testField; //shuffle(500, testField); unsigned int n; //n = testField.size(); cin >> n; //auto begin = std::chrono::high_resolution_clock::now(); // n * n(n+1) / 2 unsigned int* field = new unsigned int[FIELD_SIZE * FIELD_ROW_OFFSET]{0}; int containedFlowers = 0; for (int i = 0; i < n; i++) { string row; //cout << row << "\n"; //row = testField[i]; cin >> row; int rowSpace = i * FIELD_ROW_OFFSET; for (int k = 0; k < row.size(); k++) { int bitMask = 1 << (row[k] - 'A'); field[rowSpace + k] = bitMask; containedFlowers |= bitMask; } } ll ans = calculateAnsBitMasks2(n, field, containedFlowers); //auto end = std::chrono::high_resolution_clock::now(); cout << ans; /*vector<string> test; for (int i = 0; i < n; i++) { string text; cin >> text; test.push_back(text); }*/ //cout << "\n"; //ll bruteForceAns = bruteForce(testField); //cout << bruteForceAns; //auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count(); //std::cout << " ms: " << duration << "\n"; }
Test details
Test 1
Group: 1, 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
10 TNCTNPNTPC NPPNTNTPTP NTNTTCNTCT NPCPNPPNTT ... |
correct output |
---|
2035 |
user output |
---|
1934 |
Test 2
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
10 NFWQLWNWYS DZOQJVXFPJ CNHXPXMCQD QRTBVNLTQC ... |
correct output |
---|
9 |
user output |
---|
9 |
Test 3
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
10 XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX ... |
correct output |
---|
3025 |
user output |
---|
3025 |
Test 4
Group: 1, 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
10 FFFFFFFFFF FFFFFCFFFF FFFFFFJFFF FFFFFFFFFF ... |
correct output |
---|
12 |
user output |
---|
4 |
Test 5
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
1 X |
correct output |
---|
1 |
user output |
---|
1 |
Test 6
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 BBCBUBOUOBBCUUBBCOUO BOUCOOCUBCOOOCOBOCUO UCCUUUOBCOCBCBUBUCOO BUOBUCUCUOOBCOOUBUOO ... |
correct output |
---|
38724 |
user output |
---|
37790 |
Test 7
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 CBGLSHGZHYZDWBNDBJUG SMUXOJQYPXZDTMJUIWOJ XIDSTNBGHKRKOVUVMINB MTQGCFRUHQKALXRNCQGS ... |
correct output |
---|
8334 |
user output |
---|
2089 |
Test 8
Group: 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
20 KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK ... |
correct output |
---|
44100 |
user output |
---|
44100 |
Test 9
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 AAAAAAAAXAAAAAAAAAAA AAAWAAAAAAAAAAAAAOAA AAAAAAAAAAAAAAAAAPAA AAAAAAAAKAAAAAAAAAAZ ... |
correct output |
---|
18 |
user output |
---|
6 |
Test 10
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 GRGREEEGREGXRXXEGXXREXGRRRGRRR... |
correct output |
---|
1584665 |
user output |
---|
1575708 |
Test 11
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 AITIISJUHCCRZNKSDCNQKYSQRINFWJ... |
correct output |
---|
1077746 |
user output |
---|
427697 |
Test 12
Group: 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
50 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO... |
correct output |
---|
1625625 |
user output |
---|
1625625 |
Test 13
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF... |
correct output |
---|
1680 |
user output |
---|
280 |
Test 14
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM... |
correct output |
---|
25325366 |
user output |
---|
25284491 |
Test 15
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 LIMQQIHASECROEVILNVULGWZJPPKOG... |
correct output |
---|
22342463 |
user output |
---|
16003510 |
Test 16
Group: 4, 5, 6
Verdict: ACCEPTED
input |
---|
100 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT... |
correct output |
---|
25502500 |
user output |
---|
25502500 |
Test 17
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ... |
correct output |
---|
25650 |
user output |
---|
2868 |
Test 18
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 NAANANMMKNKKAKMKMAKNKMNKMMNNAA... |
correct output |
---|
403292767 |
user output |
---|
403126287 |
Test 19
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 OMYWATTLURKQPTKEFMGGYAOONXWVSC... |
correct output |
---|
388111321 |
user output |
---|
343307131 |
Test 20
Group: 5, 6
Verdict: ACCEPTED
input |
---|
200 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC... |
correct output |
---|
404010000 |
user output |
---|
404010000 |
Test 21
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL... |
correct output |
---|
14159445 |
user output |
---|
339518 |
Test 22
Group: 6
Verdict: WRONG ANSWER
input |
---|
500 VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW... |
correct output |
---|
15683003812 |
user output |
---|
15681915271 |
Test 23
Group: 6
Verdict: WRONG ANSWER
input |
---|
500 OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE... |
correct output |
---|
15575906951 |
user output |
---|
15160173955 |
Test 24
Group: 6
Verdict: ACCEPTED
input |
---|
500 IIIIIIIIIIIIIIIIIIIIIIIIIIIIII... |
correct output |
---|
15687562500 |
user output |
---|
15687562500 |
Test 25
Group: 6
Verdict: WRONG ANSWER
input |
---|
500 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW... |
correct output |
---|
3058970930 |
user output |
---|
35764782 |