Ruudukko

# completes tests 1 and 2, but not 3
import random
import time
import sys
from typing import Generator, TypeVar
 
 
def I():
    return map(int, input().split())
 
 
# DIVISOR = 10**9 + 7
 
_V = TypeVar("_V")
 
test_N = 1000
 
test_expected_results = {
    100: 773224951,
    200: 452330452,
    300: 37161558,
    400: 250332178,
    1000: 298053617
}
 
 
def test():
    n = test_N
 
    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 iter(list(text_gen())).__next__
 
 
# input = test()
timer_init = time.perf_counter()
 
 
class Node:
    # ended up unused
    "Binary Search Tree node"
 
    def __init__(self, parent: "Node|None", left: "Node|None", right: "Node|None", key: "int|float"):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.values = []
        self.marker = 0
        pass
 
    def Get(self) -> "list":
        return self.values
        ...
 
    def Add(self, value):
        self.values.append(value)
 
    def next(self):
        if self.marker == 0:
            self.marker += 1
            if self.left:
                return self.left
        if self.marker == 1:
            self.marker += 1
            if self.right:
                return self.right
        self.marker = 0
        return self.parent
 
 
class BST:
    # ended up unused
    def __init__(self, middle: float):
        self.root = Node(None, None, None, middle)
 
    def Insert(self, key: "int | float", value: "_V"):
 
        node, pos = self.search(key)
        if pos == 1:
            node.left = Node(node, None, None, key)
            node.left.Add(value)
        elif pos == 2:
            node.right = Node(node, None, None, key)
            node.right.Add(value)
        else:
            node.Add(value)
 
    # def Get(self, key: "int | float") -> "Node":
    #     ...
 
    def Iter(self) -> "Generator[Node,None,None]":
        node = self.root
        while 1:
            new = node.next()
            if new is None:
                break
            if node.marker == 0:
                # new is parent
                if new.marker == 1:
                    # node is left
                    yield new
            elif new.left is None:
                yield new
            # elif node.marker == 1:
            #     # new is right child
            node = new
 
    def Iter_Values(self):
        # for node in self.Iter():
        #     for x, y in node.Get():
        #         yield node.key, x, y
        return ((node.key, v) for node in self.Iter() for v in node.Get())
 
    def search(self, key: "int|float") -> "tuple[Node, int]":
        """returns a node and a number.
        0 means the node has the wanted value,
        1 means the value doesn't exist but would be the node's left branch if inserted,
        2 means the same as 1 but for the right branch."""
        # no recursion
        current = self.root
        while 1:
            if key < current.key:
                if current.left:
                    current = current.left
                else:
                    return current, 1
            elif key > current.key:
                if current.right:
                    current = current.right
                else:
                    return current, 2
            else:
                return current, 0
 
 
def main():
    DIVISOR = 10**9 + 7
 
    timer_0 = time.perf_counter()
    n, = I()
    grid = [list(I()) for _ in range(n)]
 
    timer_1 = time.perf_counter()
    print("timer 1:", timer_1 - timer_0, file=sys.stderr)
    line_row = [0] * n
    line_row_last = [1] * n
    line_col = [0] * n
    line_col_last = [1] * n
    line_row_added = [0] * n
    line_col_added = [0] * n
 
    # exists_row = [set(g) for g in grid]
    # exists_all = set().union(*exists_row)
    # print("exists_all size:", len(exists_all))
    # values_coords = BST(n * n // 2)
    sett = set((grid[y][x], x, y) for y in range(n) for x in range(n))
 
    timer_2 = time.perf_counter()
    print("timer 2:", timer_2 - timer_1, file=sys.stderr)
    sor = sorted(sett, key=lambda x: x[0])
    timer_3 = time.perf_counter()
    print("timer 3:", timer_3 - timer_2, file=sys.stderr)
 
    total = 0
    # def calculate_routes_full(number, x, y):
    for number, x, y in sor:
        if number != line_row_last[y]:
            line_row_last[y] = number
            line_row[y] += line_row_added[y]
            line_row_added[y] = 0
        if number != line_col_last[x]:
            line_col_last[x] = number
            line_col[x] += line_col_added[x]
            line_col_added[x] = 0
 
        value = (line_col[x] + line_row[y] + 1) % DIVISOR
        line_row_added[y] += value
        line_col_added[x] += value
        total += value
 
    # total = sum(calculate_routes(y, x, k)for k, x, y in sor)
    # total = sum(calculate_routes_full(*s)for s in sor)
    timer_4 = time.perf_counter()
    print("timer 4:", timer_4 - timer_3, file=sys.stderr)
 
    return total % DIVISOR
 
 
def old_iteration(n, grid, exists_row, exists_all, calculate_routes):
    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_start = time.perf_counter()
w = main()
print(w)
# 100: 773224951
# 200: 452330452
timer_end = time.perf_counter()
print("time:", timer_end - timer_start,
      ("\ncorrect" if w == test_expected_results[test_N] else "\ndifferent") if test_N in test_expected_results.keys() else "no data",
      #   "\ninit:", timer_start - timer_init,
      file=sys.stderr)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00017946097068488598
timer 2: 4.7017005272209644e-05
timer 3: 3.006309270858764...

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00017732393462210894
timer 2: 4.759302828460932e-05
timer 3: 3.084202762693167e...

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00018669094424694777
timer 2: 4.8366026021540165e-05
timer 3: 3.172503784298897...

Test 4

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.005235758959315717
timer 2: 0.008645565016195178
timer 3: 0.004282417939975858...

Test 5

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.00561907805968076
timer 2: 0.008497197995893657
timer 3: 0.004661817918531597
t...

Test 6

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.005534309078939259
timer 2: 0.00861551589332521
timer 3: 0.01238099706824869
ti...

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED