CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Lelleri
Submission time:2024-10-30 20:29:59 +0200
Language:Python3 (PyPy3)
Status:READY
Result:4
Feedback
groupverdictscore
#1ACCEPTED4
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.12 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.04 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.13 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.04 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.04 s1, 2, 3, 4, 5, 6details
#60.53 s2, 3, 4, 5, 6details
#70.24 s2, 3, 4, 5, 6details
#80.64 s2, 3, 4, 5, 6details
#9ACCEPTED0.05 s2, 3, 4, 5, 6details
#10--3, 4, 5, 6details
#11--3, 4, 5, 6details
#12--3, 4, 5, 6details
#13ACCEPTED0.14 s3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 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


def check_field(field_dimensions):
    
    for specie_key in species_coordinate_map.keys():

        right_boundary = n-field_dimensions["right"]-1
        bottom_boundary = n-field_dimensions["bottom"]-1

        for point in species_coordinate_map[specie_key]:
            if(field_dimensions["left"] <= point[0] <= right_boundary and field_dimensions["top"] <= point[1] <= bottom_boundary):
                break
        else:
            return False

            
        
    return True

def generate_unique_key(dimensions):
    return "".join(map(str, dimensions.values()))

visited_position = {}

def shrink_field(field_dimensions):


    count = 1
    for side_key in field_dimensions.keys():

        temp_field_dimensions = field_dimensions.copy()
        temp_field_dimensions[side_key] += 1

        if(visited_position.get(generate_unique_key(temp_field_dimensions), 0) == 1):
            continue

        if(check_field(temp_field_dimensions)):
            count += shrink_field(temp_field_dimensions)
            visited_position[generate_unique_key(temp_field_dimensions)] = 1

    return count

n = int(input())
field = [[l for l in input()] for _ in range(n)]


# Creating coordinate map
species_coordinate_map = {}

for y, row in enumerate(field):
    #print(" ".join(row))
    for x, point in enumerate(row):
        species_coordinate_map[point] = species_coordinate_map.get(point, []) + [(x, y)]


# Finding limits
field_dimensions = {"left": 0, "right": 0, "top": 0, "bottom": 0}

print(shrink_field(field_dimensions))

Test details

Test 1

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

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

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: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

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
34388

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
7812

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
38903

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
(empty)

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
(empty)

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
(empty)

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
(empty)

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
(empty)

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)