CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:rottis
Submission time:2024-10-30 13:51:19 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#20.00 s1, 2, 3, 4, 5, 6details
#30.00 s1, 2, 3, 4, 5, 6details
#40.00 s1, 2, 3, 4, 5, 6details
#50.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.01 s2, 3, 4, 5, 6details
#80.00 s2, 3, 4, 5, 6details
#90.01 s2, 3, 4, 5, 6details
#100.03 s3, 4, 5, 6details
#110.24 s3, 4, 5, 6details
#120.01 s3, 4, 5, 6details
#130.75 s3, 4, 5, 6details
#140.40 s4, 5, 6details
#15--4, 5, 6details
#160.07 s4, 5, 6details
#17--4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21--5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Code

#define print_board for (int i = 0; i < n; i++) { std::cout << board[i] << '\n'; } std::cout << std::endl
#define print_flowers(flowers) for (int i = 0; i < 26; i++) { std::cout << ((flowers & (1<<i)) >> i); } std::cout << '\n' << "abcdefghijklmnopqrstuvwxyz" << std::endl
#define print_rect(r) std::cout << r.left << ' ' << r.right << ' ' << r.top << ' ' << r.bottom << std::endl
#define to_bit(c) (1<<(c - 'a'))
#define MAX_RECT ((rect) { .left = 0, .right = (int16_t) (n-1), .top = 0, .bottom = (int16_t) (n-1) })
#define rect_size(r) ((1 + r.right - r.left) * (1 + r.bottom - r.top))
#define bitmap uint32_t
 
#include <iostream>
#include <stdlib.h>
#include <stdint.h>
 
// note: int16_t only needed for last part!
// other parts can do with int8_t
typedef struct {
    int16_t left;
    int16_t right;
    int16_t top;
    int16_t bottom;
} rect;
 
bool valid_rect(char **board, uint16_t n, bitmap flowers, rect rectangle) {
    bitmap flowers_in_rect = 0;
    for (uint16_t x = rectangle.left; x <= rectangle.right; x++) {
        for (uint16_t y = rectangle.top; y <= rectangle.bottom; y++) {
            flowers_in_rect = flowers_in_rect | to_bit(board[x][y]);
            if (flowers == flowers_in_rect) { return true; }
        }
    }
    return false;
}
 
int main() {
    uint16_t n;
    bitmap found_flowers = 0;
    std::cin >> n;
 
    char **board = (char**) malloc((n) * sizeof(char*));
    
    for (unsigned int i = 0; i < n; i++) {
        char *row = (char*) malloc((n+1) * sizeof(char));
        std::cin >> row;
        for (unsigned int j = 0; j < n; j++) {
            found_flowers = found_flowers | to_bit(row[j]);
        }
        board[i] = row;
    }
 
    //print_flowers(found_flowers);
    unsigned int solutions = 0;
    
    rect smallest_rect = MAX_RECT;
    
    // solutions enclosing the smallest rect need not be brute forced
    solutions += (smallest_rect.left + 1) * (n - smallest_rect.right) * (smallest_rect.top + 1) * (n - smallest_rect.bottom) - 1;
    std::cout << solutions << std::endl;
    // brute force everything smaller than that
    for (int16_t left = smallest_rect.left; left <= smallest_rect.right; left++) {
        for (int16_t right = left; right <= smallest_rect.right; right++) {
            for (int16_t top = smallest_rect.top; top <= smallest_rect.bottom; top++) {
                for (int16_t bottom = top; bottom <= smallest_rect.bottom; bottom++) {
                    if (valid_rect(board, n, found_flowers, (rect) {.left=left, .right=right, .top=top, .bottom=bottom})) {
                        solutions++;
                    }
                }
            }
        }
    } // */
 
    std::cout << solutions << std::endl;
 
    /*
    for (unsigned int i = 0; i < n; i++) {
        free(board[i]);
    }
    free(board);
    */
 
    return 0;
}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
0
2035

Test 2

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

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
0
9

Test 3

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

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
0
3025

Test 4

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

Verdict:

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
0
12

Test 5

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

Verdict:

input
1
X

correct output
1

user output
0
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
0
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
0
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
0
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
0
18

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
0
1584665

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
0
1077746

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
0
1625625

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
0
1680

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
0
25325366

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
0
25502500

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)