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 numpy as np

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

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = [0 for i in range(n)]
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= n-2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == n-1 or ga == maxga:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
_match = {}
for i in range(N):
    _match[i + 1] = [int(j) for j in input().split(' ')]

all_match_count = N * (N-1) // 2
match = []
for p, lst in _match.items():
    result = []
    for t in lst:
        if p > t:
            result.append('{}-{}'.format(t, p))
        else:
            result.append('{}-{}'.format(p, t))
    match.append(result)

#print(match)
today_match = set()
already_finish = set()
already_finish_count = 0
delete_index = {}
result = 0
while True:
    could_make_match = False
    for i in range(N):
        try:
            c = match[i][0]
        except IndexError:
            continue
        # if c in already_finish:
        #     match[i].pop(0)
        #     try:
        #         c = match[i][0]
        #     except IndexError:
        #         continue
        # 試合が見つかった
        if c in today_match:
            today_match.remove(c)
            already_finish.add(c)
            already_finish_count += 1
            match[i].pop(0)
            # print('pop', c, delete_index[c])
            match[delete_index[c]].pop(0)
            # print('match', match)
            could_make_match = True
        # 試合見つからなかった
        else:
            today_match.add(c)
            delete_index[c] = i
    if not could_make_match:
        result = -1
        break
    result += 1
    # print('day' + str(result))
    today_match = set()
    if already_finish_count == all_match_count:
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count):
    count = 0
    roop_count = 0##########
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if roop_count > 10**5:########
                        return -1#########
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0

first = a_list[:, 0]
target = n_index[first[first] == n_index].tolist()
a_index[target] += 1
for i in range(N * (N-1) // 2):
    next_target = set()
    for t in target:
        if t in next_target:
            continue
        cand = a_list[t, a_index[t]]
        if a_list[cand, a_index[cand]] == t:
            next_target.add(t)
            next_target.add(cand)

    target = list(next_target)
    a_index[target] += 1
    ans += 1
    if len(target) == 0:
        break

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
fin = [False] * N
sleep = [False] * N
An = [''] * N
deg = [0] * N
for n in range(N):
    An[n] = [int(x) for x in input().split()]

days = 0
while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in [n for n in range(N) if fin[n]==sleep[n]==False]:
        if matched[n]:
            continue
        op = An[n][deg[n]]
        if matched[op - 1]:
            continue
        if An[op - 1][deg[op - 1]] == n + 1:
            flag = True
            matched[n] = True
            matched[op - 1] = True
            deg[n] += 1
            deg[op - 1] += 1
            sleep[op - 1] = False
            if deg[n] == N - 1:
                fin[n] = True
            if deg[op - 1] == N - 1:
                fin[op - 1] = True
        else:
            sleep[n] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a = [deque([int(i) for i in input().split()]) for j in range(n)]
c = 0
gamesNum = 0
empty = False

while not empty:
  flag = [1] * n
  for i in range(n):
    if flag[i] and len(a[i]):
      opponent = a[i][0] - 1
      if flag[opponent] and len(a[opponent]) and a[opponent][0] - 1 == i:
        flag[i] = 0
        flag[opponent] = 0
        gamesNum += 1
        a[i].popleft()
        a[opponent].popleft()

  if gamesNum:
    c += 1
    gamesNum = 0
  else:
    c = -1
    break

  for i in range(n):
    if len(a[i]):
      break
    if i == n-1:
      empty = True

print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input(): return sys.stdin.readline().strip()


def solve():
    pass


def main():
    N = int(input())
    A = [[]]
    for _ in range(N):
        a = map(int, input().split())
        a = reversed(list(a))
        A.append(list(a))

    days = 0
    while any(A):
        changed = False
        matched = [False] * (N+1)
        for i in range(1, N+1):
            if matched[i] or len(A[i]) == 0:
                continue

            player1 = A[i][-1]

            for j in range(1, N+1):
                if i == j:
                    continue
                if matched[j] or len(A[j]) == 0:
                    continue

                player2 = A[j][-1]

                if player1 == j and player2 == i:
                    A[i].pop()
                    A[j].pop()
                    matched[i] = True
                    matched[j] = True
                    changed = True
                    break

        if not changed:
            print(-1)
            return

        days += 1

    print(days)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from collections import deque


def solve(N, A):
    day = 0
    total = (N * (N-1)) // 2
    players = set(range(N))
    while True:
        day += 1
        update = False
        today = set()
        loop_in_day = True
        while loop_in_day:
            loop_in_day = False
            for i in players.copy():
                if i in today:
                    continue
                if not A[i]:
                    continue
                opp = A[i][0] - 1
                if opp in today:
                    continue
                if A[opp][0] - 1 == i:
                    A[i].popleft()
                    A[opp].popleft()
                    if not A[i]:
                        players.remove(i)
                    if not A[opp]:
                        players.remove(opp)
                    today.add(i)
                    today.add(opp)
                    total -= 1
                    update = True
                    loop_in_day = True
                    if total == 0:
                        return day
        if not update:
            return -1


if __name__ == '__main__':
    N = int(input())
    A = []
    for _ in range(N):
        A.append(deque(map(int, input().split())))

    ans = solve(N, A)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    for i in range(1, N + 1):
        if Ks[i]:
            continue
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] += 1
            Cs[b] += 1
            tab.remove((a, b))
            wa.append(a)
            wa.append(b)
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d += 1
    if c == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[0]*(N-1)]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
    
B = [0]*N

hoge = 0
siai = 0
ans = 0
while siai < N*(N-1)/2:
    count = 0
    for i in range(N):
        if not len(A[i]) == 0 and not len(A[A[i][0]-1]) == 0 and A[A[i][0]-1][0]-1 == i:
            hoge = A[i][0]-1
            A[hoge].pop(0)
            A[i].pop(0)
            siai += 1
            count += 1
            if B[i] < B[hoge]:
                B[hoge] += 1
                B[i] = B[hoge]
            else:
                B[i] += 1
                B[hoge] = B[i]
            if B[i] > ans:
                ans = B[i]
    if count == 0:
        ans = -1
        break
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	while True:
		flg = False
		doList = []

		for i, val in enumerate(ind):
			#print(ind)
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			#print(A[target-1][ind[target-1]])

			if (A[target-1][ind[target-1]] - 1) == i:
				if i in doList or target-1 in doList:
					pass
				else:
					ind[i] += 1
					if ind[i] > N-2:
						ind[i] = -1

					ind[target-1] += 1
					if ind[target-1] > N-2:
						ind[target-1] = -1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			break

	for i in ind:
		if i != -1:
			print(-1)
			sys.exit()

	print(ans)



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1]: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 50000:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [list(int(_) for _ in input().split()) for i in range(n)]
l = [i+[0] for i in l]
x = [0]*n
s = set(list(range(n)))
chk = -1

for i in range(n*(n+1)+1):
    if i % 100 == 0:
        if sum(x) == chk:
            print(-1)
            break
        else:
            chk = sum(x)
    
    if len(s) == 0:
        print(i)
        break
    z = [l[ii][x[ii]] for ii in range(n)]
    sdel = set()
    for ii in s:
        if z[z[ii]-1] == ii + 1:
            if x[ii] <= n - 3:
                x[ii] = x[ii]+1
            else:
                sdel.add(ii)
    [s.remove(ii) for ii in sdel]
    if i == n*(n+1):
        print(-1)
        break

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = [int(j) - 1 for j in input().split()]
    A[i] += reversed(a)

empty = [[] for i in range(N)]
ans = 0
for _ in range(N * (N - 1) // 2):
    flag = False
    game_flag = [False] * N
    for i in range(N):
        if game_flag[i] == False and A[i] != []:
            j = A[i][-1]
            if game_flag[j] == False and A[j] != [] and A[j][-1] == i:
                flag = True
                game_flag[i] = True
                game_flag[j] = True
                A[i].pop()
                A[j].pop()
    ans += 1
    if A == empty:
        break
    elif flag == False:
        ans = -1
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [ inpl() for _ in range(N) ]
nextgame = [0] * N
day = 0
totalgames = N*(N-1)//2
donegames = 0
tomorrow_candidates = range(1,N+1)
while donegames < totalgames:
    day += 1
    readyflag = [True]*N
    todaygames = 0
    today_candidates = tomorrow_candidates
    tomorrow_candidates = set()
    for player in today_candidates:
        if not readyflag[player-1] or nextgame[player-1] >= N-1:
            continue
        opp = A[player-1][nextgame[player-1]]
        if not readyflag[opp-1]:
            continue
        opp_opp = A[opp-1][nextgame[opp-1]]
        if opp_opp == player:
            nextgame[player-1] += 1
            nextgame[opp-1] += 1
            tomorrow_candidates.add(player)
            tomorrow_candidates.add(opp)
            readyflag[player-1] = False
            readyflag[opp-1] = False
            todaygames += 1

    if todaygames == 0:
        print(-1)
        break
    else:
        donegames += todaygames
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
s=[0 for i in range(n)]
ans=0
f=0
while f < n*(n-1)//2:
  c=[0 for i in range(n)]
  ans+=1
  nf=f
  for i in range(n):
    if c[i] == 0 and s[i] < n-1 :
      x=a[i][s[i]]-1
      y=s[x]
      if c[x]==0 and a[x][y] - 1 == i:
        c[i]=1
        c[x]=1
        s[x]+=1
        s[i]+=1
        f+=1
  if f==nf:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0 for i in range(N)]
	ans = 0

	while True:
		flg = False
		doList = []

		for i, val in enumerate(ind):
			#print(ind)
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			#print(A[target-1][ind[target-1]])

			if (A[target-1][ind[target-1]] - 1) == i:
				if i in doList or target-1 in doList:
					pass
				else:
					ind[i] += 1
					if ind[i] > N-2:
						ind[i] = -1

					ind[target-1] += 1
					if ind[target-1] > N-2:
						ind[target-1] = -1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			break

	for i in ind:
		if i != -1:
			print(-1)
			sys.exit()

	print(ans)



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

def main():
    A_list = []
    if 'LOCAL' in os.environ:
        N = 1000
        for i in range(N):
            tmp = [j for j in range(N) if i != j]
            random.shuffle(tmp)
            A_list.append(tmp)

    else:
        N = _I()
        for i in range(N):
            A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx, A in enumerate(A_list):
        new_A_list[aidx] = tuple(i-1 for i in A)
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = {i:0 for i in range(N)}
    done_player_list = set()
    position_sum = 0
    done_sum = (N-1)*N
    #  all_done_players = set()
    while True:
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

        for i in range(N-1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if i in done_player_list:
                continue

            #  if i in all_done_players:
            if current_position_list.get(i) == N-1:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list.get(i)[current_position_list.get(i)]
            if opponent_idx in done_player_list:
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list[opponent_idx][current_position_list[opponent_idx]] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                done_player_list.add(opponent_idx)
                done_player_list.add(i)
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                #  if current_position_list[i] == N-1:
                #      all_done_players.add(i)
                #  if current_position_list[opponent_idx] == N-1:
                #      all_done_players.add(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

        if not is_ok:
            # 1試合も成立しなかったらストップする
            print(-1)
            exit()

        done_player_list = set()
        current_day += 1

    print(current_day)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [list(map(int,input().split())) for i in range(N)]

day = 0
judge = 1
length = [N-1 for i in range(N)]
sum = (N-1)*N
while judge != 0:
	list = []
	for i in range(N):
		if length[i] > 0:
			if a[a[i][0]-1][0] == i+1:
				list.append(i)
	for i in list:
		a[i].pop(0)
		length[i] -= 1
		sum  -= 1
	day += 1
	#print(list)
	
	if len(list) == 0:
		if sum == 0:
			print(day-1)
			exit()
		else:
			print(-1)
			exit()

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count):
    count = 0
    roop_count = 0##########
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if roop_count > 10**6:########
                        return -1#########
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n=int(input())
a=[[]]
for i in range(n):
    ai = deque(list(map(int,input().split())))
    a.append(ai)
ans=0
while(True):
    empty_lists=0
    battled_i=[]
    for i in range(1,len(a)):
        if(len(a[i]) == 0):
            empty_lists+=1
            continue

        next_i = a[i][0]

        if(i in battled_i or next_i in battled_i):
            continue

        if(a[next_i][0] == i):
            a[i].popleft()
            a[next_i].popleft()
            battled_i.append(i)
            battled_i.append(next_i)

    if(empty_lists == n):
        break
    elif(len(battled_i) == 0):
        print(-1)
        sys.exit()
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    bbb = 0

    for i in range(n):
        if ls[i] != -1:
            mt[i] = a[i][ls[i]]

    for w in range(10 ** 15):
        cnt += 1
        bb = False
        update = []
        f = [False] * n
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        bb = True
                        f[i] = True
                        f[mt[i]-1] = True
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            update.append(i)
                        else:
                            ls[i] = -1
                            bbb += 1

                        if ls[mt[i]-1] + 1 < n - 1:
                            ls[mt[i]-1] += 1
                            update.append(mt[i]-1)
                        else:
                            ls[mt[i]-1] = -1
                            bbb += 1
        for i in update:
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        if bbb == n:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

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

match_num = (n * (n - 1)) // 2
match_cnt = 0

fin = [0 for _ in range(n)]
update = True
day = 0
while True:
    update = False
    day += 1
    skip = set()
    for i, d in enumerate(fin):
        if i in skip:
            continue
        if d >= n-1:
            continue

        op = league[i][d]
        me = league[op][fin[op]]

        if op in skip:
            continue

        if i == me:
            update = True
            match_cnt += 1
            fin[i] += 1
            fin[op] += 1
            skip.add(me)
            skip.add(op)

    if match_cnt == match_num:
        break

    if not update:
        day = -1
        break

print(day)