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:
import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [[i for i in range(n_game) if indegree[i] == 0], []]
n_ts = 0
while cand[ans%2]:
    n_ts += len(cand[ans%2])
    cand[(ans+1)%2] = []
    for ci in cand[ans%2]:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand[(ans+1)%2].append(v)
    ans += 1

if n_ts != n_game:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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

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

def main(N, A):
    now = [-1]*N
    day = 0
    rest = N * (N-1) // 2

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(N)
        if rest == 0:
            return day

        # if not terminal make new now
        # O(N)
        for i in range(N):
            if now[i] == -1 and len(A[i]) > 0:
                now[i] = A[i].pop()
        
        # see if we have match today
        have_match = False
        # O(N)
        for i in range(N):
            if now[i] != -1 and now[now[i]-1] - 1 == i:
                now[now[i]-1] = -1
                now[i] = -1
                rest -= 1
                have_match = True
        if not have_match:
            return -1
        day += 1

print(main(N, A))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
      c[b[i]-1]+=1
  #print('c='+str(c))
  for i in range(N):
    b[i]=a[i][c[i]//2]
  #print('b='+str(b))
  cnt+=1
  if c==[(N-1)*2]*N:
    print(cnt)
    exit()

print('-1')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]!=i+1:
      if i==b[b[i]-1]-1:
        c[i]+=1
        c[b[i]-1]+=1
  #print('c='+str(c))
  for i in range(N):
    b[i]=a[i][c[i]//2]
  #print('b='+str(b))
  cnt+=1
  if c==[(N-1)*2]*N:
    print(cnt)
    exit()

print('-1')

Submission status: Time Limit Exceeded

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

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

def main(N, A):
    now = [-1]*N
    day = 0
    while True:
        # terminal condition
        count = 0
        for i in range(N):
            if len(A[i]) == 0:
                count += 1
        if count == N:
            return day

        # if not terminal make new now
        for i in range(N):
            if now[i] == -1 and len(A[i]) > 0:
                now[i] = A[i].pop()
        
        # see if we have match today
        have_match = False
        for i in range(N):
            if now[i] != -1 and now[now[i]-1] - 1 == i:
                now[now[i]-1] = -1
                now[i] = -1
                have_match = True
        if not have_match:
            return -1
        day += 1

print(main(N, A))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
match_list = deque([])

for i in range(n):
    match_list.append(deque(map(lambda x: int(x), input().split())))

days = 1

while True:
    match_collection = [0] * n
    for i in range(n):
        if len(match_list[i]) == 0:
            continue
        else:
            match_candidate_a, match_candidate_b = i, match_list[i][0]-1
            if len(match_list[match_candidate_b])>0 and match_list[match_candidate_b][0]-1 == match_candidate_a and match_collection[match_candidate_a] == 0 and match_collection[match_candidate_b] == 0:
                match_list[match_candidate_a].popleft()
                match_list[match_candidate_b].popleft()
                match_collection[match_candidate_a] = 1
                match_collection[match_candidate_b] = 1
    
    if sum(match_collection) == 0:
        days = -1
        break
    else:
        remains = 0
        for j in range(n):
            remains += len(match_list[j])
        
        if remains > 0:
            days += 1
        else:
            break
            
print(days)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque

input = sys.stdin.readline

n = int(input())
a = [deque(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]) == 0:
        o = a[p][0]
        if a[o][0] == p:
            if p > o : p , o = o, p
            if not (p, o) in q:
                q.append((p, o))

for p in range(n):
    check(p, q)

while len(q) > 0:
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:
        a[o].popleft()
        a[p].popleft()
        check(p, q)
        check(o, q)


if all(map(len, a)):
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
def set_to_tuple(x):
    x = list(x)
    x.sort()
    return tuple(x)


n = int(input())
schedule = [map(int, input().split()) for _ in range(n)]
node = {}
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        node[set_to_tuple({i, j})] = [set(), set()]
for i in range(1, n + 1):
    for j, opponent in enumerate(schedule[i - 1]):
        if j == 0:
            buf = opponent
        else:
            node[set_to_tuple({buf, i})][1].add(set_to_tuple({opponent, i}))
            node[set_to_tuple({opponent, i})][0].add(set_to_tuple({buf, i}))
            buf=opponent
count = (n * (n - 1)) // 2
flag = True
ans = 0
while flag and count != 0:
    day = []
    for key, edge in node.items():
        if edge[0] == set():
            day.append(key)
    if len(day) == 0:
        flag = False
    else:
        count -= len(day)
        ans += 1
    for key in day:
        for next_node in node[key][1]:
            node[next_node][0].remove(key)
        del node[key]
if flag:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

N = int(input())
As = [list(map(int,input().split())) for i in range(N)]
As = np.array(As)-1
current_waitings = As[:,0]
game_counter = np.zeros(N).astype('int')

day = 0
completed_players = []
res = N*(N-1)//2
while res:
    day_player = []
    no_game = True
    for i,e1 in enumerate(current_waitings):
        if i in completed_players or e1 in day_player or i in day_player:
            continue
        if current_waitings[e1] == i:
            no_game = False
            res -= 1
            day_player.append(i)
            day_player.append(e1)
            if game_counter[i] == N-2:
                completed_players.append(i)
            if game_counter[i] <= N-3:
                game_counter[i] += 1
            if game_counter[e1] == N-2:
                completed_players.append(e1)
            if game_counter[e1] <= N-3:
                game_counter[e1] += 1
            current_waitings[i] = As[i][game_counter[i]]
            current_waitings[e1] = As[e1][game_counter[e1]]
    if no_game:
        print(-1)
        sys.exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

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

As = np.array(As)-1


current_waitings = As[:,0]

game_counter = np.zeros(N).astype('int')

day = 0
completed_players = []
res = N*(N-1)//2
while res:
    day_player = []
    no_game = True
    for i,e1 in enumerate(current_waitings):
        if i in completed_players:
            continue
        if current_waitings[e1] == i and e1 not in day_player and i not in day_player:
            no_game = False
            res -= 1
            day_player.append(i)
            day_player.append(e1)
            if game_counter[i] == N-2:
                completed_players.append(i)
            if game_counter[i] <= N-3:
                game_counter[i] += 1
            if game_counter[e1] == N-2:
                completed_players.append(e1)
            if game_counter[e1] <= N-3:
                game_counter[e1] += 1
            current_waitings[i] = As[i][game_counter[i]]
            current_waitings[e1] = As[e1][game_counter[e1]]
    if no_game:
        print(-1)
        sys.exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    D = []
    for i in range(1,N+1):
        D.append(i)
        
    while count < N*(N-1)//2 and flag == 0:
        flag = 1
        for i in D:
            if B[i] < N:
                j = A[i][B[i]]
                if A[j][B[j]] == i:
                    k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
                    C[i][B[i]] = k
                    C[j][B[j]] = k
                    B[i] += 1
                    if B[i] == N:
                        D.remove(i)
                    B[j] += 1
                    if B[j] == N:
                        D.remove(j)
                    count += 1
                    flag = 0
                    
    #print(C)
    ans = 0
    for i in C:
        if i[-1] > ans:
            ans = i[-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 愚直解

import sys
input = sys.stdin.readline

N = int(input())

A = [ [int(i) for i in input().split() ] for j in range(N) ]

for i in range(N):
	A[i].append(-1)
	A[i] = [int(s) for s in A[i]]



# Hはリスト
def search(H):
	list=[]
	counter = 0
	for i in range(N):
		if H.count(i+1) > 0:

			l = [k for k, x in enumerate(H) if x == i+1]
			
			# lengh_l = len(l)

			# for j in range(lengh_l):
			# 	if H[i] == l[j]+1 and l[j] > i:

			if l.count(H[i] -1) > 0 and i < H[i] - 1:
				ans = H[i] - 1 


				list.append((i,ans))
				counter += 1
				

	list.append(counter)
	return list

depth_col = [0]*N

look = []

for _ in range(N):
	look.append(A[_][0])

counter = 0

while min(depth_col) < N-1:
	result = search(look)

	if result[-1] == 0:
		counter = -1
		break
	else:
		lengh_search = len(result)-1
		for j in range(lengh_search):
			x = result[j][0]
			y = result[j][1]
			# print(x)
			# print(y)
			depth_col[x] += 1
			depth_col[y] += 1

			a = depth_col[x]
			b = depth_col[y]
			look[x] = A[x][a]
			look[y] = A[y][b]

		counter += 1

if counter < 0:
	print(-1)
else:
	print(counter)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n*(n-1)//2):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    while count < N*(N-1)//2 and flag == 0:
        flag = 1
        for i in range(1,N+1):
            if B[i] < N:
                j = A[i][B[i]]
                if A[j][B[j]] == i:
                    k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
                    C[i][B[i]] = k
                    C[j][B[j]] = k
                    B[i] +=  1
                    B[j] += 1
                    count += 1
                    flag = 0
                    
    #print(C)
    ans = 0
    for i in C:
        if i[-1] > ans:
            ans = i[-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    f = defaultdict(lambda : 0)
    flg,flg2 = False,False
    for i in range(n):
        if len(a[i]) == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        if f[(y,x)] == 1:
            flg = True
            f[(y,x)] = 0
        else:
            f[(x,y)] = 1
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
    for k,l in f.items():
        if l > 0:
            a[k[0]-1].appendleft(k)
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    ans = 0
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    while count < N*(N-1)//2 and  flag == 0:
        flag = 1
        for i in range(1,N+1):
            if B[i] < N:
                j = A[i][B[i]]
                if A[j][B[j]] == i:
                    k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
                    C[i][B[i]] = k
                    C[j][B[j]] = k
                    B[i] +=  1
                    B[j] += 1
                    count += 1
                    flag = 0
                    break
    #print(C)
    ans = 0
    for i in C:
        if i[-1] > ans:
            ans = i[-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)
    
    
    
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(100000):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2 - 2*n):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2 - n):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
cnt = [n-1]*n
for j in range(n**2):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if cnt[i] == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        cnt[i] -= 1
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
            cnt[y-1] -= 1
        else:
            a[i].appendleft((x,y))
            cnt[i] += 1
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in range(n):
    if cnt[i] != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [ [int(i) for i in input().split() ] for j in range(N) ]

for i in range(N):
	A[i].append(-1)
	A[i] = [int(s) for s in A[i]]



# Hはリスト
def search(H):
	list=[]
	counter = 0
	for i in range(N):
		if H.count(i+1) > 0:

			l = [k for k, x in enumerate(H) if x == i+1]
			
			lengh_l = len(l)

			for j in range(lengh_l):
				if H[i] == l[j]+1 and l[j] > i:
					list.append((i,l[j]))
					counter += 1
					break

	list.append(counter)
	return list

depth_col = [0]*N

look = []

for _ in range(N):
	look.append(A[_][0])

counter = 0

while min(depth_col) < N-1:
	result = search(look)

	if result[-1] == 0:
		counter = -1
		break
	else:
		lengh_search = len(result)-1
		for j in range(lengh_search):
			x = result[j][0]
			y = result[j][1]
			# print(x)
			# print(y)
			depth_col[x] += 1
			depth_col[y] += 1

			a = depth_col[x]
			b = depth_col[y]
			look[x] = A[x][a]
			look[y] = A[y][b]

		counter += 1

if counter < 0:
	print(-1)
else:
	print(counter)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2+1):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
k=0
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    ans+=1
    IsMatch=False
    done=set()
    #print('Day',ans,IsMatch,nx)
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            #print('Day',ans,'Match',c1,'vs',c2)
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
            #print('i,t,d',i,t,'done=',done,'nx=',nx,n_i,n_n_i)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    check = [1]*n
    flg = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
from queue import Queue
todo = [0] * (n+1)
matched = Queue()
for i in range(1, n+1):
    matched.put(i)
days = 0
while True:
    update = []
    while matched.empty() == False:
        i = matched.get()
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
                update.append(p)
    for j in update:
        todo[j] += 1
        matched.put(j)
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)