CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Pikaksi
Submission time:2024-11-09 18:09:44 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.18 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.18 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.18 s1, 2, 3, 4, 5, 6details
#40.18 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.18 s1, 2, 3, 4, 5, 6details
#60.18 s2, 3, 4, 5, 6details
#70.18 s2, 3, 4, 5, 6details
#8ACCEPTED0.19 s2, 3, 4, 5, 6details
#90.19 s2, 3, 4, 5, 6details
#100.18 s3, 4, 5, 6details
#110.18 s3, 4, 5, 6details
#12ACCEPTED0.18 s3, 4, 5, 6details
#130.19 s3, 4, 5, 6details
#140.19 s4, 5, 6details
#150.19 s4, 5, 6details
#16ACCEPTED0.19 s4, 5, 6details
#170.19 s4, 5, 6details
#180.20 s5, 6details
#190.24 s5, 6details
#20ACCEPTED0.20 s5, 6details
#210.22 s5, 6details
#220.46 s6details
#230.93 s6details
#24ACCEPTED0.43 s6details
#250.95 s6details

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:

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:

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:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
37790

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

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:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
6

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1575708

Test 11

Group: 3, 4, 5, 6

Verdict:

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:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
280

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
25284491

Test 15

Group: 4, 5, 6

Verdict:

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:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
2868

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
403126287

Test 19

Group: 5, 6

Verdict:

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:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
339518

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
15681915271

Test 23

Group: 6

Verdict:

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:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
35764782