CSES - Datatähti 2023 alku - Results
Submission details
Task:Ruudukko
Sender:okkokko
Submission time:2022-11-04 18:26:01 +0200
Language:Python3 (CPython3)
Status:READY
Result:61
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED33
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.02 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.03 s2, 3details
#5ACCEPTED0.12 s2, 3details
#6ACCEPTED0.10 s2, 3details
#7ACCEPTED0.80 s3details
#8--3details
#9--3details

Code

# completes tests 1 and 2, but not 3
import random
import time
import sys
def I():
return map(int, input().split())
DIVISOR = 10**9 + 7
def test():
n = 400
def text_gen():
yield str(n)
random.seed(1001)
for i in range(n):
yield " ".join((str(random.randint(1, n * n)) for _ in range(n)))
return text_gen().__next__
# input = test()
count_row_skip_1 = 0
count_col_skip_1 = 0
def main():
timer_0 = time.perf_counter()
n, = I()
grid = [list(I()) for _ in range(n)]
total = 0
timer_1 = time.perf_counter()
line_values_row = [0] * n
line_values_row_last_used_high = [1] * n
line_values_col = [0] * n
line_values_col_last_used_high = [1] * n
line_values_row_added = [0] * n
line_values_col_added = [0] * n
exists_row = [{grid[y][x] for x in range(n)} for y in range(n)]
exists_col = [{grid[y][x] for y in range(n)} for x in range(n)]
exists_all = set().union(*exists_col)
# print("exists_all size:", len(exists_all))
def get_line_values_row(y: int, v: int):
"""tells how many routes can start from a tile of value v and first go along row y \n
sum of the route values of tiles less than v on row y"""
if v == line_values_row_last_used_high[y]: # false <==> first time with this y and v
global count_row_skip_1
count_row_skip_1 += 1
return line_values_row[y]
line_values_row_last_used_high[y] = v
s = line_values_row[y] + line_values_row_added[y]
line_values_row_added[y] = 0
line_values_row[y] = s
return s
def get_line_values_col(x: int, v: int):
if v == line_values_col_last_used_high[x]:
global count_col_skip_1
count_col_skip_1 += 1
return line_values_col[x]
line_values_col_last_used_high[x] = v
s = line_values_col[x] + line_values_col_added[x]
line_values_col_added[x] = 0
line_values_col[x] = s
return s
def calculate_routes(y: int, x: int, number: int):
if number == 1:
value = 1
else:
value = (get_line_values_col(x, number) + get_line_values_row(y, number) + 1) % DIVISOR
nonlocal total
total += value
line_values_row_added[y] += value
line_values_col_added[x] += value
timer_2 = time.perf_counter()
for a in range(1, n * n + 1):
if a not in exists_all:
continue
for y in range(n):
if a not in exists_row[y]:
continue
x = -1
try:
while True:
x = grid[y].index(a, x + 1)
calculate_routes(y, x, a)
except ValueError:
pass
timer_3 = time.perf_counter()
print("timer 1:", timer_1 - timer_0, "\ntimer 2:", timer_2 - timer_1, "\ntimer 3:", timer_3 - timer_2, file=sys.stderr)
def summod(x):
return sum(y % DIVISOR for y in x) % DIVISOR
# w = summod(map(summod, route_grid))
# assert w == total % DIVISOR
# return w
return total % DIVISOR
timer_start = time.perf_counter()
w = main()
print(w)
print("time:", time.perf_counter() - timer_start,
"\nsame" if w == 452330452 else "\ndifferent",
"\nrow skips:", count_row_skip_1,
"\ncol skips:", count_col_skip_1, file=sys.stderr)

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 1 1
1 1 1
1 1 1

correct output
9

user output
9

Error:
timer 1: 4.161603283137083e-05 
timer 2: 2.1043000742793083e-05 
timer 3: 1.86119577847421...

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 3
6 5 4
7 8 9

correct output
135

user output
135

Error:
timer 1: 4.474801244214177e-05 
timer 2: 5.157798295840621e-05 
timer 3: 3.539503086358309...

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
7 8 1
4 5 4
3 9 6

correct output
57

user output
57

Error:
timer 1: 4.383799387142062e-05 
timer 2: 2.8542010113596916e-05 
timer 3: 3.36379744112491...

Test 4

Group: 2, 3

Verdict: ACCEPTED

input
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
10000

user output
10000

Error:
timer 1: 0.0015807609888724983 
timer 2: 0.0013367850333452225 
timer 3: 0.004592943994794...

Test 5

Group: 2, 3

Verdict: ACCEPTED

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
187458477

user output
187458477

Error:
timer 1: 0.0020168949849903584 
timer 2: 0.003983793023508042 
timer 3: 0.0964820159715600...

Test 6

Group: 2, 3

Verdict: ACCEPTED

input
100
2995 8734 1018 2513 7971 5063 ...

correct output
964692694

user output
964692694

Error:
timer 1: 0.0020689809462055564 
timer 2: 0.003949727048166096 
timer 3: 0.0711492099799215...

Test 7

Group: 3

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1000000

user output
1000000

Error:
timer 1: 0.12968235200969502 
timer 2: 0.14714699698379263 
timer 3: 0.5009190510027111
ti...

Test 8

Group: 3

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
229147081

user output
(empty)

Test 9

Group: 3

Verdict:

input
1000
520283 805991 492643 75254 527...

correct output
951147313

user output
(empty)