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
from collections import deque
def main():
    N=int(input())
    L=[[]]
    
    for i in range(N):
        a=deque(map(int,input().split()))
        L.append(a)
    #print(L)
    
    day=0
    cnt=0
    for i in range(10**6+5):
        if cnt==N*(N-1)/2:
            break
        D=dict()
        CNT=0
        for j in range(1,N+1):
            #print(L[j],j)
            if len(L[j])==0 or j in D:
                continue
            elif L[L[j][0]][0]==j and L[j][0] not in D:
                D[j]=1
                D[L[j][0]]=1
                X=L[j][0]
                L[j].popleft()
                L[X].popleft()
                CNT+=1
        if CNT==0:
            print(-1)
            exit()
        cnt+=CNT
        day+=1
    #print(L)
    #print(cnt)
    print(day)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
n = int(input())
a = collections.deque()
for i in range(n):
    k = collections.deque([int(x) for x in input().split()])
    a.append(k)
ans = 0
key = 0
while a:
    s = 1
    todaylist = []
    for i in range(n):
        if i+1 in todaylist:
            continue
        if a[i]:
            if a[i][0] in todaylist:
                continue
            b = a[i][0]-1
            if a[b]:
                if a[b][0] == i+1:
                    a[i].popleft()
                    a[b].popleft()
                    todaylist.append(i+1)
                    todaylist.append(b+1)
                    s = 0
    ans += 1
    key += 1
    if s:
        print(-1)
        sys.exit()
    if key >= n-1 and not any(a):
        break
print(ans)

Submission status: Time Limit Exceeded

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

days = 0

remains = sum(len(a[i]) for i in range(n))
while True:
    if remains == 0:
        break
    days += 1
    played = []
    for i in range(n):
        if i in played:
            continue
        if len(a[i]) > 0:
            op = a[i][0] - 1
            if op in played:
                continue
            if a[op][0] - 1 == i:
                del a[i][0]
                del a[op][0]
                played.append(i)
                played.append(op)
                remains -= 2;

    if len(played) == 0:
        days = -1
        break

print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a
    

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    while True:
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]
            if  A[enemy-1][IDX[enemy-1]] == player+1:
                next_idx = i+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = i
        if flag:
            return -1
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

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

	for i in range(10000000):
		flg = False
		doList = []

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

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

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

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						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:
from collections import deque

N = int(input())
Ass = deque(deque(map(int, input().split())) for _ in range(N))

dp = [0 for _ in range(N)]
flag = True
while flag:
    flag = False
    for i, As in enumerate(Ass):
        if not As:
            continue
        t = As[0] - 1
        if Ass[t][0] == i + 1:
            Ass[t].popleft()
            As.popleft()
            dp[t] = dp[i] = max(dp[t], dp[i]) + 1
            flag = True
if any(Ass):
    print(-1)
else:
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]


cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
while True:
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

while A != [[0]] * N :
  #print([[0]] * N)
  finish = [0] * N
  for i in range(N):
    #print(A, i)
    if A[i][0] != 0:
      if (A[A[i][0] - 1][0] == i + 1) and (finish[i] == 0) and (finish[A[i][0]-1] == 0): #対戦可能な場合対戦。
        x = A[i][0]
        A[i].pop(0)
        A[x - 1].pop(0)
        finish[i] = 1
        finish[x-1] = 1
        if len(A[i]) == 0:
          A[i].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
li=[list(map(int,input().split())) for i in range(n)]
np_list=np.array(li).T
np_list=np.append(np_list,np.array([-1 for _ in range(n)]))
np_list=np_list.reshape(n,-1)
li=[0 for i in range(n)]
day=0

while(True):
  if sum(li)==n*(len(np_list)-1):
    print(day)
    break
  charange=[np_list[li[i],i]-1 for i in range(n)]
  count=0
  for i in range(len(charange)):
    if charange[charange[i]]==i:
      count+=1
      li[i]+=1
      li[charange[i]]+=1
      charange[i]=-1
  if count==0:
    print(-1)
    break
  else:
    day+=1

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque

sys.setrecursionlimit(10000000)

n = int(sys.stdin.readline().rstrip())
a = [deque(map(int, sys.stdin.readline().split())) for _ in range(n)]

def deepPop(x):
    global a
    global days
    target = a[x][0] -1
    if a[target][0] -1 == x:
        a[target].popleft()
        a[x].popleft()
        maxd = max(days[x] +1, days[target] +1)
        days[x] = maxd
        days[target] = maxd
        if len(a[x]) > 0:
            deepPop(x)
        if len(a[target]) > 0:
            deepPop(target)


day = 0
days = [0] * n
setn = set(range(n))
while True:
    popped = 0
    zeros = 0
    tmpns = copy.copy(setn)
    for i in setn:
        if len(a[i]) == 0:
            tmpns.remove(i)
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if a[num][0] - 1 == i:
            deepPop(i)
            popped += 1
    if popped == 0:
        if len(tmpns) == 0:
            break
        else:
            day = -1
            break
    setn = tmpns

if day == -1:
    print(day)
else:
    print(max(days))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = 0
count = 0
MAX_COUNT = n * (n-1)
iteration_times = 0
flag = 0

while iteration_times <= MAX_COUNT:
    # print(L)
    # print(count)
    iteration_times += 1

    if count == MAX_COUNT:
        flag = 1
        break
    
    numset = set()
    for i in range(n):
        if len(L[i]) != 0:
            a = L[i][0]
            b = L[a][0]
            if i == b:
                numset.add(i)
                numset.add(b)
    for elm in numset:
        L[elm].popleft()
        count += 1

    ans += 1

if flag == 1:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
P = [0] * N
g = [0]
ans = 0
while len(g) > 0:
    g = []
    for i in range(N):
        if i in g:
            continue
        j = A[i][P[i]] - 1
        if j in g:
            continue
        if A[j][P[j]] - 1 == i:
            if N - 2 > P[i]:
                P[i] += 1
                g.append(i)
            if N - 2 > P[j]:
                P[j] += 1
                g.append(j)
    ans += 1
for p in P:
    if p != N - 2:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
while True :
    rmv = set()
    #print(a)
    for i in range(len(a)) :
        if len(a[i]) == 0 :
            continue
        index = a[i][0] - 1
        #print(i, index)
        if a[index][0] == i + 1:
            #print('koko')
            #print(index, i)
            rmv.add(index)
            rmv.add(i)
    if len(rmv) == 0 :
        print(-1)
        exit()
    #print(a, rmv)
    for elem in rmv :
        a[elem].pop(0)
    #print(a)
    cnt += 1

    flag = True
    for i in range(n) :
        if len(a[i]) != 0 :
            flag = False
    if flag :
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def p_e():
    N = int(input())
    A = [deque(map(lambda x: x - 1, map(int, input().split()))) for _ in range(N)]
    m = N * (N - 1) / 2

    ans = 0
    while True:
        idx = []

        for i in range(N):
            if not A[i]:
                continue

            if i == A[A[i][0]][0]:
                idx.append(i)

        if not idx:
            break

        for i in idx:
            A[i].popleft()
        ans += 1

        if ans > m:
            break

    for a in A:
        if a:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def map_all(es):
    return all([e == es[0] for e in es[1:]]) if es else False

if __name__ == '__main__':
    N = int(input())
    A = [deque(map(int, input().split())) for i in range(N)]
    today = []
    flag=False
    
    for d in range(N*(N-1)//2):
        for me in range(1, N+1):
            if len(A[me-1]) != 0:
                opp = A[me-1][0]
                if A[opp-1][0] == me:
                    today.append(me)


        for n in today:
            A[n-1].popleft()
        today = []
        
        if map_all(A):
            flag=True
            break
    if flag:
        print(d+1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[:]
    

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    while True:
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]
            if  A[enemy-1][IDX[enemy-1]] == player+1:
                next_idx = i+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = i
        if flag:
            return -1
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

X = []
N = int(input())
for i in range(N):
	A = getlist()
	X.append([0] + A[::-1])

#日数
day = 0
while True:
	j = "No"
	check = [0] * N
	for i in range(N):
		x = X[i][-1] - 1
		if x != -1:
			if check[i] == 0 and check[x] == 0 and X[x][-1] == i + 1:
				check[i] = 1
				check[x] = 1
				X[x].pop(-1)
				X[i].pop(-1)
				j = "Yes"
	day += 1
	if j == "No":
		break

#判定
cc = "Yes"
for i in range(N):
	if X[i] != [0]:
		cc = "No"
		break

if cc == "No":
	print(-1)
else:
	print(day - 1)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count, more_play):
    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 more_play[i] 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 len(A_lst[p1]) == 0:
                        more_play[p1] = False
                    if len(A_lst[p2]) == 0:
                        more_play[p2] = False
                    if roop_count > 10**4:########
                        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)
more_play = [True]*(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, more_play)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
import sys

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

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    while True:
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

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
H = [0] * N

while A != [[0]] * N :
  #print([[0]] * N)
  finish = [0] * N
  for i in range(N):
    #print(A, i)
    if len(A[i]) != 0:
      if (A[A[i][0] - 1][0] == i + 1) and (finish[i] == 0) and (finish[A[i][0]-1] == 0): #対戦可能な場合対戦。
        x = A[i][0]
        A[i].pop(0)
        A[x - 1].pop(0)
        finish[i] = 1
        finish[x-1] = 1
        if len(A[i]) == 0:
          A[i].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

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 = []
    e = N + 1
    f = N - 1
    for i in range(1, e):
        if Ks[i] or Cs[i] == f:
            continue
        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] = Cs[a] + 1
            Cs[b] = 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 = d + 1
    if c == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=defaultdict(deque)
    for i in range(n):
        d[i+1]=deque(map(int,input().split()))

    c=0
    immortalskip=set()
    while any(d.values()):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy() and i not in immortalskip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
#            print(c,i,d,skip,f)
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    op = [[]]
    for i in range(N):
        op.append(deque(list(map(int, input().split()))))

    day = 0
    ok = 1
    count = (N * (N - 1)) // 2
    can = 1
    while True:
        if not ok:
            day = -1
            print('ok')
            break
        if count == 0:
            break
        if can == 0:
            day = -1
            break
        played = [0] * (N + 1)
        k = 1
        k_seen = 1
        end_day = 0
        can = 0
        while True:
            if len(op[k]) > 0:
                opponent = op[k][0]
                if len(op[opponent]) > 0:
                    if op[opponent][0] == k:
                        if played[k] == 0 and played[opponent] == 0:
                            count -= 1
                            can = 1
                            op[k].popleft()
                            op[opponent].popleft()
                        played[k] = 1
                        played[opponent] = 1
                        k_seen += 1
                        k = k_seen
                        while played[k] == 1:
                            k += 1
                            if k >= N:
                                day += 1
                                end_day = 1
                                break
                    else:
                        played[k] = 1
                        if played[opponent] == 0:
                            k = opponent
                        else:
                            k_seen += 1
                            k = k_seen
                            while played[k] == 1:
                                k += 1
                                if k >= N:
                                    day += 1
                                    end_day = 1
                                    break
                else:
                    ok = 0
                    break
            else:
                played[k] = 1
                k_seen += 1
                k = k_seen
                while played[k] == 1:
                    k += 1
                    if k >= N:
                        day += 1
                        end_day = 1
                        break
            if end_day == 1:
                break

    print(day)


if __name__ == '__main__':
    main()

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 % 1000 == 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 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)
nm2 = n - 2
nm1 = n - 1
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = [0] * n
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= nm2:
            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 == nm1 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 copy

N = int(input()) # 数字を変数に格納
tmp_list = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

day = 0
flag = 1

while tmp_list != [[]]*N:
    done = [0]*N
    day += 1
    flag = 0
    
    for i in range(N-1):
        if done[i] == 0 and len(tmp_list[i]) != 0:
            next = tmp_list[i][0]-1
            if tmp_list[next][0] == i+1 and done[next] == 0:
                done[i] = 1
                done[next] = 1
                del tmp_list[i][0]
                del tmp_list[next][0]
                flag = 1
    if flag == 0:
        break

if flag == 0:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

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

total = N*(N-1)//2
progress = [0]*N
battled = [False]*N
any_battle = False
day = 1
finished = 0
battle_count = 0
for _ in range(total+1):
    for man in range(N):
        if progress[man] >= N-1:
            continue
        rival = A[man][progress[man]] - 1
        if battled[man] or battled[rival]:
            continue
        if A[rival][progress[rival]] - 1 == man:
            progress[man] += 1
            progress[rival] += 1
            battled[man], battled[rival] = True, True
            any_battle = True
            if progress[man] == N-2:
                finished += 1
            if progress[rival] == N-2:
                finished += 1
            battle_count += 1
            if battle_count == total:
                break
    battled = [False]*N
    day += 1
    if finished == N:
        print(day)
        break
    if not any_battle:
        print(-1)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int, input().split())) for i in range(N)]
s=[]
for i in range(N):
    s.append([A[i][0],0])
a=0
while s!=[None]*N:
    l=[]
    for i in range(N):
        if s[i]!=None:
            if s[s[i][0]-1][0]==i+1:
                l.append(i)
    if l==[]:
        print(-1)
        break
    else:
        for i in l:
            if s[i][1]!=N-2:
                s[i]=[A[i][s[i][1]+1],s[i][1]+1]
            else:
                s[i]=None
    a+=1
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
a=[[int(i)-1 for i in input().split()] for _ in range(n)]
day_check=[False for _ in range(n)]
day_cnt=0
match_cnt=0
while match_cnt<n*(n-1)//2:
    day_cnt+=1
    today_check=copy.copy(day_check)
    for i in range(n):
        if not a[i]:
            continue
        if today_check[i]:
            continue
        m=a[i][-1]
        if a[m][-1]==i and not today_check[m]:
            match_cnt+=1
            today_check[i]=True
            today_check[m]=True
            a[i].pop(-1)
            a[m].pop(-1)
    if not any(today_check):
        print(-1)
        exit()
print(day_cnt)

Submission status: Time Limit Exceeded

Solution code:
def seek_candidates(current_A):
    can_set = []
    for n in range(N):
        if(current_A[n+1] != []):
            if(current_A[current_A[n+1][0]][0] == n + 1):
                can_set.append(set([n+1, current_A[n+1][0]]))
    return can_set

def make_next_A(current_A, battles):
    next_A = current_A
    for battle in battles:
        for b in battle:
            next_A[b] = current_A[b][1:]
    return next_A

def make_battle_set(can_set):
    battle_set = []
    battle_players = set()
    for c in can_set:        
        if(c & battle_players == set()):
            battle_set.append(list(c))
            battle_players = battle_players | c
    return battle_set

import collections

A = collections.Counter()
N = int(input())
for n in range(N):
    A[n+1] = list(map(int, input().split()))

success_flag = False
loop_count = 0
currnet_A = A
remain_battles = int(N*(N-1)/2)

while(True):
    loop_count += 1
    can_set = seek_candidates(currnet_A)
    if(can_set == []):
        break
    battle_set = make_battle_set(can_set)
    currnet_A = make_next_A(currnet_A, battle_set)
    remain_battles -= len(battle_set)
    if(remain_battles <= 0):
        success_flag = True
        break
if(success_flag):
    print(loop_count)
else:
    print(-1)