Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

import sys
input = sys.stdin.readline


n = int(input())
a_list = {i:None for i in range(n)}
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k > j:
                    if k not in visit:
                        if a_list[k][0] == j:
                            num += 1
                            visit.add(a_list[j].popleft())
                            visit.add(a_list[k].popleft())
                        if num >= n * (n - 1) // 2:
                            print(day)
                            exit()
    if (len(visit) == 0):
        print(-1)
        exit()
    if num >= n * (n - 1) // 2:
        print(day)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():

    n = int(input())
    a = [tuple(map(int, input().split())) for _ in range(n)]

    adj = defaultdict(list)
    in_deg = defaultdict(int)
    for u, row in enumerate(a, 1):
        for v1, v2 in zip(row, row[1:]):
            uu1, vv1 = min(u, v1), max(u, v1)
            uu2, vv2 = min(u, v2), max(u, v2)
            match1 = uu1 + vv1 * 1000
            match2 = uu2 + vv2 * 1000
            adj[match1].append(match2)
            in_deg[match1]
            in_deg[match2] += 1

    now = [key for key, val in in_deg.items() if val == 0]
    day = 0
    while now:
        day += 1
        nxt = []
        for u in now:
            for v in adj[u]:
                in_deg[v] -= 1
                if in_deg[v] == 0:
                    nxt.append(v)

        now = nxt

    if max(in_deg.values()) > 0:
        day = -1

    print(day)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        adj[(uu1, vv1)].append((uu2, vv2))
        in_deg[(uu1, vv1)]
        in_deg[(uu2, vv2)] += 1

now = [tpl for tpl, val in in_deg.items() if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit, number remain(not 0 exists)
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1)
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit, number remain(not 0 exists)
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1) 
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]


# トポロジカルソート
for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit number remain
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1) 
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]
        if costs[direction_in_topological_sorted] < 1+now_cost:
            costs[direction_in_topological_sorted] = 1+now_cost
        if max_cost < costs[direction_in_topological_sorted]:
            max_cost = costs[direction_in_topological_sorted]
print(max_cost+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]


# トポロジカルソート
for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit number remain
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1) 
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]
        if costs[direction_in_topological_sorted] < 1+now_cost:
            costs[direction_in_topological_sorted] = 1+now_cost
        if max_cost < costs[direction_in_topological_sorted]:
            max_cost = costs[direction_in_topological_sorted]
print(max_cost+1)

Submission status: Time Limit Exceeded

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

##キューの管理のどこがおかしいかわからなかったがあきらめる

can={i for i in range(n)}
nxt=set()
Done = set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in Done and a[i]:
            p = a[i][-1]
            if p not in Done:##この判定しないと1日に複数回試合することになる
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    Done.add(p);Done.add(i)
                    rem-=1
                    nxt.add(i);nxt.add(p)

    can=nxt.copy()###copy
    Done=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
A = []
for i in range(n):
    rs  = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(deque(rs))

listed = [-1] *  n
cnt = 1
while True:
    matched = False
    for i in range(n):
        if listed[i] == -1 and len(A[i]) > 0:
            #i番目のqueueから最新を取り出す
            listed[i] = A[i].popleft() 
    # tmp = []
    for i in range(n):
        aite = listed[i]
        # すでにその日試合していたらout
        if listed[i] == -1:continue
        if i == listed[aite]:
            listed[i] = -1
            listed[aite] = -1
            matched = True
            # tmp.append((i,aite))
    # print(tmp)
    if not matched:
        print(-1)
        exit()
    if all([len(r) == 0 for r in A]):
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N  = int(input())
ll = []
for i in range(N):
    l = [int(x) for x in input().split()]
    ll.append(l)
a = [[0 for i in range(2)] for j in range(N+1)]
for i in range(N):
    a[i+1][0] = ll[i][0]
    a[i+1][1] = 1
end = 0
ans = 0
z = 0
while True:
    ok = 0
    tai = [0]*(N+1)
    ans += 1
    for i in range(1,N+1):
        now = a[i][0]
        if tai[i] != 0:
            continue
        if tai[now] != 0:
            continue
        if a[now][0] == i and now > i:
            ok += 1
            tai[i] = 1
            tai[now] = 1
            if a[now][1] == N-1:
                end += 1
            else:
                a[now][0] = ll[now-1][a[now][1]]
                a[now][1] += 1
            if a[i][1] == N-1:
                end += 1
            else:
                a[i][0] = ll[i-1][a[i][1]]
                a[i][1] += 1
    if end == N:
        print(ans)
        break
    if ok == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    _A = [[]*N for _ in range(N)]

    for i in range(N):
        _A[i] = deque(list(map(int,input().split())))


    A = deque(_A)
    ans = 0
    empty_count = 0

    def search(i,ignore_i):
        empty_count = 0
        found = False
        vs = set()
        a = A[i]
        if len(a) == 0: return False,set(),0

        target_i = a[0]-1
        if target_i in ignore_i or i in ignore_i: return False,set(),0

        target = A[target_i]
        if len(target) == 0:
            print(-1)
            exit()

        # print(ans,":",i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
        if target[0]-1 == i:
            found = True
            _, _ = target.popleft(), a.popleft()

            if len(a) == 0:
                empty_count += 1
            if len(target) == 0:
                empty_count += 1

            ignore_i.add(i)
            ignore_i.add(target_i)

            vs.add(i)
            vs.add(target_i)

        return found, vs, empty_count


    found = False
    vs = set()
    ignore_i = set()

    for i in range(N):
        res = search(i,ignore_i)
        found = res[0] or found
        # print(res[1])
        vs = vs.union(res[1])
        empty_count += res[2]

    ans += 1
    if not found:
        print(-1)
        exit()


    while empty_count < N:
        found = False
        ignore_i = set()
        new_vs = set()
        for i in vs:
            res = search(i,ignore_i)
            found = res[0] or found
            new_vs = new_vs.union(res[1])
            empty_count += res[2]

        vs = new_vs
        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    _A = [[]*N for _ in range(N)]

    for i in range(N):
        _A[i] = deque(list(map(int,input().split())))


    A = deque(_A)
    ans = 0
    empty_count = 0

    while empty_count < N:
        found = False
        ignore_i = set()
        for i in range(N):
            a = A[i]
            if len(a) == 0: continue

            target_i = a[0]-1
            if target_i in ignore_i or i in ignore_i: continue

            target = A[target_i]
            if len(target) == 0:
                print(-1)
                exit()

            # print(ans,":",i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
            if target[0]-1 == i:
                found = True
                _, _ = target.popleft(), a.popleft()

                if len(a) == 0:
                    empty_count += 1
                if len(target) == 0:
                    empty_count += 1

                ignore_i.add(i)
                ignore_i.add(target_i)



        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    _A = [[]*N for _ in range(N)]

    for i in range(N):
        _A[i] = deque(list(map(int,input().split())))


    A = deque(_A)
    ans = 0
    empty_count = 0

    while empty_count < N:
        found = False
        ignore_i = set()
        for i in range(N):
            a = A[i]
            if len(a) == 0: continue

            target_i = a[0]-1
            if target_i in ignore_i or i in ignore_i: continue

            target = A[target_i]
            if len(target) == 0:
                print(-1)
                exit()

            # print(ans,":",i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
            if target[0]-1 == i:
                found = True
                _, _ = target.popleft(), a.popleft()

                if len(a) == 0:
                    empty_count += 1
                if len(target) == 0:
                    empty_count += 1

                ignore_i.add(i)
                ignore_i.add(target_i)



        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i+1]].append(b[i])

    go = [False]*((N*(N-1))//2)
    cul = [False]*((N*(N-1))//2)
    dp = [0]*((N*(N-1))//2)
    
    def dfs(v):
        if go[v]:
            if not cul[v]:
                return -1
            return dp[v]
        go[v] = True
        dp[v] = 1
        for u in edge[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v],ret+1)
        cul[v] = True
        return dp[v]
    
    ans = 0
    for i in range((N*(N-1))//2):
        ret = dfs(i)
        if ret == -1:
            print(-1)
            exit()
        ans = max(ans,ret)
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = []
for _ in range(n):
  A.append(list(map(int,input().split())))

current_node = [0 for _ in range(n)]
ongoing = [i for i in range(n)]
days = 0
def get_matched_one(tmp):
  i = tmp.pop(0)
  i_current = current_node[i]
  if i_current >= n-1:
    return None, tmp
 #   print(i, i_current, len(A[i]))
  opponent = A[i][i_current] - 1
  opponent_current = current_node[opponent]
  matched = None
  if i == A[opponent][opponent_current] - 1:
    matched = [i, opponent]
    tmp.remove(opponent)
  return matched, tmp

def get_matched():
  matched = []
  tmp = [o for o in ongoing]
  while tmp:
    m, tmp = get_matched_one(tmp)
    if m:
      matched.append(m)
  return matched

def proceed(matched):
  done = 0
  for m in matched:
    current_node[m[0]] += 1
    current_node[m[1]] += 1
    if current_node[m[0]] == n-1:
      done += 1
      ongoing.remove(m[0])
    if current_node[m[1]] == n-1:
      done += 1
      ongoing.remove(m[1])
  return done

matched = get_matched()
done = 0
while done != n and matched:
  done += proceed(matched)
  days += 1
  matched = get_matched()
  
if done == n:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = []
for _ in range(n):
  A.append(list(map(int,input().split())))

current_node = [0 for _ in range(n)]
ongoing = [i for i in range(n)]
days = 0
def get_matched():
  matched = []
  for i in ongoing:
    i_current = current_node[i]
    if i_current >= n-1:
      continue
 #   print(i, i_current, len(A[i]))
    opponent = A[i][i_current] - 1
    opponent_current = current_node[opponent]
    if i == A[opponent][opponent_current] - 1:
      matched.append([i, opponent])
  return matched

def proceed(matched):
  done = 0
  for m in matched:
    current_node[m[0]] += 1
    if current_node[m[0]] == n-1:
      done += 1
      ongoing.remove(m[0])
  return done

matched = get_matched()
done = 0
while done != n and matched:
  done += proceed(matched)
  days += 1
  matched = get_matched()
  
if done == n:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = []
for _ in range(n):
  A.append(list(map(int,input().split())))

current_node = [0 for _ in range(n)]
ongoing = [i for i in range(n)]
days = 0
def get_matched():
  matched = []
  for i in range(n):
    i_current = current_node[i]
    if i_current >= n-1:
      continue
 #   print(i, i_current, len(A[i]))
    opponent = A[i][i_current] - 1
    opponent_current = current_node[opponent]
    if i == A[opponent][opponent_current] - 1:
      matched.append([i, opponent])
  return matched

def proceed(matched):
  done = 0
  for m in matched:
    current_node[m[0]] += 1
    if current_node[m[0]] == n-1:
      done += 1
      ongoing.remove(m[0])
  return done

matched = get_matched()
done = 0
while done != n and matched:
  done += proceed(matched)
  days += 1
  matched = get_matched()
  
if done == n:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = []
for _ in range(n):
  A.append(list(map(int,input().split())))

current_node = [0 for _ in range(n)]
days = 0
def get_matched():
  matched = []
  for i in range(n):
    i_current = current_node[i]
    if i_current >= n-1:
      continue
 #   print(i, i_current, len(A[i]))
    opponent = A[i][i_current] - 1
    opponent_current = current_node[opponent]
    if i == A[opponent][opponent_current] - 1:
      matched.append([i, opponent])
  return matched

def proceed(matched):
  done = 0
  for m in matched:
    current_node[m[0]] += 1
    if current_node[m[0]] == n-1:
      done += 1
  return done

matched = get_matched()
done = 0
while done != n and matched:
  done += proceed(matched)
  days += 1
  matched = get_matched()
  
if done == n:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in range(n):
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  for k in r:
    m[k].pop()
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os,io
import collections
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=collections.deque(list(map(int,input().split())))
  m.append(a)
ans=0
count=0
failflag=0
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in range(n):
    if m[i]:
      t=m[i][0]
      if m[t-1]:
        if m[t-1][0]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  for k in r:
    m[k].popleft()
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os,io
import collections
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=collections.deque(list(map(int,input().split())))
  m.append(a)
ans=0
count=0
failflag=0
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in range(n):
    if m[i]:
      if m[m[i][0]-1]:
        if m[m[i][0]-1][0]==i+1:
          count+=1
          r.add(i)
          r.add(m[i][0]-1)
  for k in r:
    m[k].popleft()
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = list(map(lambda x: int(x) - 1, input().split()))

    # print(A)

    days = 0
    while True:
        ta = []
        aset = set()
        for i in range(N):
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta.append(i)
                ta.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta) > 0:
            for t in ta:
                A[t].pop(0)
            days += 1
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = list(map(lambda x: int(x) - 1, input().split()))

    # print(A)

    days = 0
    while True:
        ta = []
        for i in range(N):
            if len(A[i]) == 0 or i in ta:
                continue
            if i == A[A[i][0]][0]:
                ta.append(i)
                ta.append(A[i][0])
        if len(ta) > 0:
            for t in ta:
                A[t].pop(0)
            days += 1
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()