Niitty

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...

#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 calculateAnsBitMasksFast(const unsigned int n, unsigned int* const field, const unsigned int containedFlowers)
{
    unsigned long long ans = 0;
    const int nTriangleSize = n * (n + 1) / 2;
    unsigned int* calculatedDepth = new unsigned int[nTriangleSize];
 
    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";
    //cout << "ans at start = " << ans << "\n"; 
 
    for (unsigned int y = 0; y < n - 1; y++) { // loop rows
        unsigned int rowSpace = y * FIELD_ROW_OFFSET;

        for (int i = 0; i < nTriangleSize; i++) {
            calculatedDepth[i] = y;
        }
        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";
                if (currentOrTowerIndex == n - currentOrTower - 1) {
                    break;
                }

                int depth = calculatedDepth[triangleTraverser];
                //cout << "depth = " << depth << " ";
                for (int i = depth + 1; i <= orRowIndex; i++) {
                    //cout << i << " ";
                    field[rowSpace + triangleTraverser] |= field[i * FIELD_ROW_OFFSET + triangleTraverser];
                }
                calculatedDepth[triangleTraverser] = orRowIndex;

                //cout << " flowers = " << flowers << " at = " << (rowSpace + triangleTraverser) << " ";

                int flowers = field[rowSpace + triangleTraverser];
                if (flowers == containedFlowers) {
                    ans += n - currentOrTower - currentOrTowerIndex;

                    if (currentOrTower == 0) {
                        //cout << "valid at tower = 0\n";
                        currentOrTowerIndex += 1;
                        triangleTraverser += 1;
                    }
                    else {
                        //cout << "valid at tower >= 1\n";
                        triangleTraverser -= n - currentOrTower;
                        currentOrTower -= 1;
                        currentOrTowerIndex += 1;
                    }
                }
                else {
                    //cout << "not valid\n";
                    triangleTraverser += n - currentOrTower;
                    currentOrTower += 1;
                }
            }
            //cout << "ans = " << ans << "\n";
        }
    }

    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() % 26 + 'A';
        }
        //cout << "row = " << row << "\n";
        testField[i] = row;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //vector<string> testField = {"AAAAA", "AAAAA", "AABAA", "AAACA", "AAADA"};
    //vector<string> testField = {"BAA", "AAB", "AAA"};
    //vector<string> testField = {"Z"};
    //vector<string> testField = {"BC", "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;

    // n * n(n+1) / 2
    unsigned int* field = new unsigned int[FIELD_SIZE * FIELD_ROW_OFFSET]{0};
    
    char input[FIELD_SIZE + 1];
    int containedFlowers = 0;
    for (int i = 0; i < n; i++) {
        string row = testField[i];
        //scanf("%s", input);
        //gets(input);
        //string row; cin >> row;
        //cin >> input;
        //getline(cin, row);
        
        //cout << row << "\n";
        //printf("%s", input);
 
        int rowSpace = i * FIELD_ROW_OFFSET;
        for (int k = 0; k < n; k++) {
            //cout << input[k];
            int bitMask = 1 << (row[k] - 'A');
            field[rowSpace + k] = bitMask;
            containedFlowers |= bitMask;
        }
    }
    auto begin = std::chrono::high_resolution_clock::now();
    ll ans = calculateAnsBitMasksFast(n, field, containedFlowers);
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count();
    std::cout << " ms: " << duration << "\n";
    cout << ans;
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 6

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: WRONG ANSWER

Test 23

Group: 6

Verdict: WRONG ANSWER

Test 24

Group: 6

Verdict: WRONG ANSWER

Test 25

Group: 6

Verdict: WRONG ANSWER