CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:valtteriilola
Submission time:2018-10-13 16:15:05 +0300
Language:Python3
Status:READY
Result:31
Feedback
groupverdictscore
#1ACCEPTED31
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.06 s1details
#7ACCEPTED0.07 s1details
#8ACCEPTED0.07 s1details
#9ACCEPTED0.07 s1details
#10ACCEPTED0.07 s1details
#11ACCEPTED0.06 s2details
#12ACCEPTED0.05 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.06 s2details
#150.05 s2details
#160.05 s2details
#170.06 s2details
#180.05 s2details
#190.06 s2details
#200.05 s2details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details
#26--3details
#27--3details
#28--3details
#29--3details
#30--3details

Code

from itertools import permutations
from math import factorial
import functools
from sys import exit


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

class _Any:
    __slots__ = ()

    def __eq__(self, other):
        return True

Any = _Any()


@functools.lru_cache(maxsize=500)
def derangement(n):
    if n == 1:
        return 0
    if n == 0:
        return 1
    
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))

if all(set(row) == {'.'} for row in board):
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
    exit(0)


indices_a = []
indices_b = []
for row in board:
    try:
        indices_a.append(row.index('A'))
    except ValueError:
        indices_a.append(Any)

    try:
        indices_b.append(row.index('B'))
    except ValueError:
        indices_b.append(Any)

total = 0
for p1 in permutations(range(n)):
    for p2 in permutations(range(n)):
        if any(x == y for x, y in zip(p1, p2)):
            continue

        if not all(x == y for x, y in zip(p1, indices_a)):
            continue
        
        if not all(x == y for x, y in zip(p2, indices_b)):
            continue
        
        total += 1

print(total)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...

correct output
12

user output
12

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....

correct output
216

user output
216

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
...

correct output
5280

user output
5280

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
...

correct output
264

user output
264

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
...

correct output
22

user output
22

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
...

correct output
2

user output
2

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
...

correct output
1

user output
1

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
...

correct output
306442892

user output
306442892

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................

correct output
694861480

user output
694861480

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................

correct output
555319110

user output
555319110

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................

correct output
108372237

user output
108372237

Test 15

Group: 2

Verdict:

input
333
.................................

correct output
259107857

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 16

Group: 2

Verdict:

input
444
.................................

correct output
19906314

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 17

Group: 2

Verdict:

input
497
.................................

correct output
224313667

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 18

Group: 2

Verdict:

input
498
.................................

correct output
929574601

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 19

Group: 2

Verdict:

input
499
.................................

correct output
600226043

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 20

Group: 2

Verdict:

input
500
.................................

correct output
198353194

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  File "input/code.py", line 26, in derangement
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))
  [Previous line repeated 328 more times]
  File "input/code.py", line 21, in derangement
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Test 21

Group: 3

Verdict:

input
499
.................................

correct output
840243733

user output
(empty)

Test 22

Group: 3

Verdict:

input
499
........................A........

correct output
4146290

user output
(empty)

Test 23

Group: 3

Verdict:

input
499
B.........A......................

correct output
173518884

user output
(empty)

Test 24

Group: 3

Verdict:

input
499
...A....B........................

correct output
20044800

user output
(empty)

Test 25

Group: 3

Verdict:

input
499
AB...............................

correct output
2

user output
(empty)

Test 26

Group: 3

Verdict:

input
500
.................................

correct output
121064146

user output
(empty)

Test 27

Group: 3

Verdict:

input
500
.................................

correct output
848435259

user output
(empty)

Test 28

Group: 3

Verdict:

input
500
.....B........A..................

correct output
296240911

user output
(empty)

Test 29

Group: 3

Verdict:

input
500
.A......B........................

correct output
2196

user output
(empty)

Test 30

Group: 3

Verdict:

input
500
...AB............................

correct output
1

user output
(empty)