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:
# -*- 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(500000):
		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:
N = int(input())
A = {}
for i in range(N):
    A[i] = list(map(lambda x: int(x)-1, input().split()))

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    not_played = set(range(N))
    for j in range(N):
        if len(A[j]) == 0 or j not in not_played or A[j][0] not in not_played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            not_played.remove(t1)
            not_played.remove(A[t1].pop(0))
            games += 1
            games_amount += 1
        if games*2 >= N:
            break
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
print(days)

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()
        A_list = [LI() for i in range(N)]
        #  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()
    N_1 = N - 1
    for _ in range(10**7):
        #  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 += (opponent_idx, i)
                done_player_list.add(i)
                done_player_list.add(opponent_idx)
                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 = {-1,}
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys

  sys.setrecursionlimit(10**7)
  readline = sys.stdin.readline

  
  n = int(readline())
  a = [list(map(int,readline().split())) for _ in range(n)]
  c = [0]*n
  d = 0
  m = set(range(n))
  
  while m:
    candidate = set()
    for i in m:
      if i in candidate:
        continue
      j = a[i][c[i]]-1
      if a[j][c[j]]-1 == i:
        candidate.add(i)
        candidate.add(j)

    if candidate:
      for i in candidate:
        c[i]+=1
        if c[i] == n-1:
          m.remove(i)
      d+=1
    else:
      d=-1
      break
      
  print(d)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())

n2 = []

for i1 in range(n1):
    n2.append([int(i) for i in input().split()])

n3 = [0] * n1
r1 = 0

for i2 in range(500000):
    t1 = 0
    r1 += 1
    d1 = {}
    for i3 in range(n1 - 1):
        if n3[i3] >= n1 - 1:
            continue
        t2 = n2[i3][n3[i3]] - 1
        if n2[t2][n3[t2]] == (i3 + 1) and i3 < t2 and d1.get(i3, 0) == 0 and d1.get(t2, 0) == 0:
            n3[i3] += 1
            n3[t2] += 1
            d1[i3] = 1
            d1[t2] = 1
            t1 = 1

    if min(n3) >= (n1 - 1):
        break
    if t1 == 0:
        r1 = -1
        break

print(r1)

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()
wa = [0] * (N + 1)
while sw:
    wac = 0
    c = 0
    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))
            Ks[a] = False
            wa[wac] = b
            wac = wac + 1
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in range(N):
        if wa[i] == 0:
            break
        Ks[wa[i]] = False
        wa[i] = 0
    d = d + 1
    if c == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
N = int(input())
A = {}
for i in range(1,N+1):
    A[i] = deque(map(int,input().split()))
# print(A)

GAME = N*(N-1)//2
cnt = 0
ans = 0
cnt2 = 0
while cnt < GAME:
    s = set(range(1,N+1))
    while s:
        i = s.pop()
        if A[i]:
            t = A[i][0]
            if t in s and A[t] and i == A[t][0]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                s = s - set([t])
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

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

N = int(input())
A = [0]*N

for i in range(N):
    X = deque(list(map(int,input().split())))
    X = deque([i+1,X[j]] for j in range(N-1))
    A[i] = X

res = 0
cnt = 0
pcnt = [N-1]*N
m = N*(N-1)//2
while 1:
    prev = cnt
    flag = [0]*N
    for i in range(N):
        if flag[i] == 0 and pcnt[i] != 0:
            X = A[i][0]
            ind = X[1]-1
            if pcnt[ind] != 0:
                if A[ind][0] == X[::-1] and flag[ind] == 0:
                    A[i].popleft()
                    A[ind].popleft()
                    flag[i] = 1
                    flag[ind] = 1
                    cnt += 1
                    pcnt[i] -= 1
                    pcnt[ind] -= 1
    if cnt == prev:
        res = -1
        break
    else:
        res += 1
        if cnt == m:
            break
print(res)

Submission status: Time Limit Exceeded

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

output = 0
memo = [0] * N
newmemo = [0] * N
owari = [0] * N
flag = 0
while flag < N:
    ng = 0
    for i in range(N):
        check = A[i][memo[i]]-1
        if i==A[check][memo[check]]-1:
            if memo[i] < N-2:
                newmemo[i]+=1
            elif (memo[i] == N-2) and (owari[i]==0):
                owari[i] = 1
                flag += 1
            else:
                continue
        else:
            ng += 1
    if ng == N:
        output = -1
        break
    memo = newmemo[:]
    output += 1

print(output)

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[i]==-1:
      continue
    if charange[charange[i]]==i:
      count+=1
      li[i]+=1
      li[charange[i]]+=1
      charange[charange[i]]=-1
  if count==0:
    print(-1)
    break
  else:
    day+=1

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
A=collections.defaultdict(list)
for i in range(1,N+1):
    aij=list(map(int,input().split()))
    A[i] = aij

uses = [0] * (N+1)

#print(A)
#for i in range(1,N+1):
#    print(A[i])
donotchange=False
day=0
while True:
    day_change=False
    used = [False] * (N+1)
    for i in range(1,N+1):
        if used[i] == False and uses[i] < N-1:
#            print(str(i)+','+str(uses[i]))
            target = A[i][uses[i]]
            target_top = A[target][uses[target]]
#            print('source:'+str(i)+',target:'+str(target)+',target_top:'+str(target_top))

            if target_top == i and used[target]==False:
#                print('ok')
                used[i] = True
                used[target] = True
                uses[i]+=1
                uses[target]+=1
                day_change=True
            else:
#                print('ng')
                pass
    
    day+=1

    if day_change==False:
        donotchange=True
        break

    isend=True
    for i in range(1,N+1):
        if uses[i] < N-1:
            isend=False
            break
    if isend==True:
        break

if donotchange==True:
    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 i in range(N)]
index = [0]*(N+1)

ans = -1
for _ in range(600000):
    today = [True]*(N+1)
    flag = 0
    for j in range(N):
        if not today[j+1]:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if today[j+1] and today[opponent] and A[opponent-1][index[opponent]] == j+1:
            index[opponent] += 1
            index[j+1] += 1
            today[opponent] = False
            today[j+1] = False
            flag = 1
    ans += 1
    if flag == 0:
        if sum(index) == N*(N-1):
            break
        else:
            ans = -1
            break
    #print(index)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())

AA = [deque(list(map(int, input().split()))) for _ in range(N)]
# print(AA)
next_play = []
today_plan = [0] * N

next_play = [AA[i][0] for i in range(N)]


ans = 0
while True:
    game = False
    for i in range(N):
        if today_plan[i] == -1:
            continue
        aite = next_play[i]
        if next_play[aite - 1] == -1 or aite == -1:
            continue

        if (i+1) == next_play[aite-1] and today_plan[aite-1] != -1:
            today_plan[i], today_plan[aite - 1] = -1, -1
            game = True
            AA[i].popleft()
            AA[aite - 1].popleft()

            if len(AA[i]) != 0:
                next_play[i] = AA[i][0]
            else:
                next_play[i] = -1
            if len(AA[aite - 1]) != 0:
                next_play[aite - 1] = AA[aite - 1][0]
            else:
                next_play[aite - 1] = -1

    if game is False:
        print(-1)
        exit()
    else:
        today_plan = [0] * N
    ans += 1
    if next_play == [-1] * N:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
nt = []
for i in range(n):
  tmp = list(map(int, input().split()))
  nt.append(tmp)

day = 0
j = np.zeros(n,dtype = int)
  
while(True):
  #print(j)
  tmp = []
  tmp2 = []
  for i in range(n):
    if j[i] < n-1:
      tmp2.append(i)
      if nt[nt[i][j[i]]-1][j[nt[i][ j[i] ]-1]] == i+1:
      	tmp.append(i)
  #print(tmp)
  if len(tmp) == 0:
    if len(tmp2) != 0:
      day = -1
    break
  for i in tmp:
    j[i] += 1
  day += 1
  

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [deque([int(s) for s in input().split()]) for i in range(N)]
count = 0
ismatch = False
while True:
  ismatch_list = [False for i in range(N)]
  if sum([len(a) for a in A]) == 0:
    break
  for i in range(N):
    if A[i] == deque([]) or ismatch_list[i] == True:
      pass
    elif A[A[i][0]-1][0] == i+1 and ismatch_list[A[i][0]-1] == False:
      ismatch = True
      ismatch_list[A[i][0]-1] = True
      ismatch_list[i] = True
      A[A[i][0]-1].popleft()
      A[i].popleft()
  if ismatch:
    count += 1
    ismatch = False
  else:
    count = -1
    break
print(count)

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(1000000):
		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:
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:
#!/usr/bin/env python

import sys
from collections import deque

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= deque( [ int(x)-1 for x in sys.stdin.readline().split() ] )
#
tot= (n*(n-1))//2
now= 0
c= 0
flags= [ False for _ in range(n) ]
while True:
    for i in range(n):
        if flags[i]: continue
        ai = a[i]
        if len(ai)==0: continue
        j  = ai[0]
        aj = a[j]
        if aj[0]==i:
            flags[i]= True
            flags[j]= True
            now+= 1
    #
    if not any(flags): break
    for i in range(n):
        if flags[i]:
            flags[i]= False
            a[i].popleft()
    #
    c+= 1
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0]
for i in range(1,N+1):
    A.append([int(x) for x in input().split()] + [0])

date = 0
match = 0
OK = True
while match < N*(N-1)//2:
    temp = set()
    for i in range(1,N):
        j = A[i][0]
        if j > i:
            if A[j][0] == i:
                temp.add(i)
                temp.add(j)
                match += 1
    if temp == set():
        OK = False
        break
    for i in temp:
        A[i].pop(0)
    date += 1

if OK:  print(date)
else: print(-1)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    from collections import deque
    A = [deque(map(int,input().split())) for _ in range(N)]
    days = 0
    idxs = [0] * N
    while True:
        #print(A)
        firstgame = True
        # desired = [ A[i][idxs[i]] for i in range(N)]
        desired = [ A[i][0] for i in range(N)]
        # desired = []
        # for i in range(N):
        #     idx = idxs[i]
        #     l = A[i]
        #     #print(N,idx)
        #     desired.append(l[idx])
        # print(desired)

        if desired.count(-1) == N:
            print(days)
            return

        for i in range(N):
            
            a = desired[i]
            if a < 0:
                continue
            b = desired[a-1]
            # a = A[i][0]
            # if a < 0:
            #     continue
            # b = A[a-1][0]
            if b < 0:
                continue
            # matched
            if b == i+1:
                A[a-1].popleft()
                if len(A[a-1]) == 0:
                    A[a-1].append(-1)
                A[i].popleft()
                if len(A[i]) == 0:
                    A[i].append(-1)
                desired[a-1] = -1

                # idxs[i] += 1
                # if idxs[i] == N-1:
                #     idxs[i] = N-2
                #     A[i][-1] = -1

                # desired[a-1] = -1
                # A[a-1][idxs[a-1]] = -1

                # idxs[a-1] += 1
                # if idxs[a-1] == N-1:
                #     idxs[a-1] = N-2
                #     A[a-1][-1] = -1
                
                if firstgame:
                    firstgame = False
                    days += 1
        if firstgame:
            print(-1)
            return 
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n):
  l1=list(map(int,input().split()))
  l[i+1]=l1
b=True
day=0
lcount=[0 for i in range(n+1)]
lcount[0]=n-1
while b and min(lcount)!=n-1:
  day+=1
  todaygame=[1 for i in range(n+1)]
  for i in range(1,n+1):
    if lcount[i]==-1+n:
      pass
    elif lcount[l[i][lcount[i]]]==-1+n:
      pass
    else:
      j=l[i][lcount[i]]
      if l[j][lcount[j]]==i:
        if todaygame[i]==1  and todaygame[j]==1:
          todaygame[i]=0
          todaygame[j]=0
                           
          lcount[i]+=1
          lcount[j]+=1
                         
  if todaygame==[1 for i in range(n+1)]:
    b=False
  else:
    todaygame=[1 for i in range(n+1)]
if b:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = list(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
    for j in update:
        todo[j] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
def seek_candidates(current_A):
    can_set = []
    seeked_set = set()
    for n in range(N):
        if(n+1 not in seeked_set):
            if(current_A[n+1] != []):
                if(current_A[current_A[n+1][0]][0] == n + 1):
                    tmp = set([n+1, current_A[n+1][0]])
                    can_set.append(tmp)
                    seeked_set = seeked_set | tmp
    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)

Submission status: Time Limit Exceeded

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

day = 0
fin_players = []
while(True):
    players = []
    fin_count = 0
    for i,match in enumerate(match_l):
        if(not match):
            fin_count += 1

        elif(match_l[match[0]-1]):
            if(match_l[match[0]-1][0]-1==i):
                players.append(i)

    if(fin_count == N):
        print(day)
        exit(0)
    if(not players):
        print(-1)
        exit(0)

    for player in players:
        match_l[player].pop(0)
        if(not match_l[player]):
            fin_players.append(player)

    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
                    roop_count += 1########
            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)
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:
N = int(input())
A = [[int(i)-1 for i in input().split()] for _ in range(N)]

idx = [0] * N
finished = [False] * N
days = 0
while True:
  if all(finished):
    print(days)
    exit()
  days += 1
  lst = []
  for i in range(N):
    if finished[i] == True:
      continue
    else:
      select = A[i][idx[i]]
      if A[select][idx[select]] == i:
        lst.append(i)
  for i in range(len(lst)):
    if idx[lst[i]] == N-2:
      finished[lst[i]] = True
    else:
      idx[lst[i]] += 1
  if len(lst) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

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

N = int(input())
A = []
for i in range(N):
    Ax = [x - 1 for x in map(int, input().split(" "))]
    A.append(Ax)

day = 0
while(True):
    day += 1
    # マッチしている物同士はとりあえず試合させる
    matched = []
    for i in range(N):
        if not A[i]:
            continue
        m = A[i][0]
        if m > i and len(A[m]) and A[m][0] == i:
            matched.append(i)
            matched.append(m)
    if not matched:
        day = -1
        break
    for i in matched:
        A[i].pop(0)
    if not any(map(len, A)):
        break

print(day)