Ruudukko

# 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 1

Group: 1, 2, 3

Verdict: ACCEPTED

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

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

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

Test 4

Group: 2, 3

Verdict: ACCEPTED

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

Test 5

Group: 2, 3

Verdict: ACCEPTED

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

Test 6

Group: 2, 3

Verdict: ACCEPTED

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

Test 7

Group: 3

Verdict: ACCEPTED

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

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED