Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [list(map(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 or battled[man]:
            continue
        rival = A[man][progress[man]] - 1
        if 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:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque

  N = int(input())
#  table = [list(map(int, input().split())) for i in range(N)]
  table = []
  for i in range(N):
    H = deque()
    A = input().split()
    for a in A:
      H.append(int(a))
    table.append(H)      
  count = 0
#  cur = [0]*N
  for k in range(10**6):
    flag = 0
    game = [0]*N
    count += 1
    for i in range(N):
      if game[i] == 0 and len(table[i]) != 0:
        x = table[i][0]-1
        if game[x] == 0 and table[x][0] == i+1:
#          print(count,i,x)
          table[i].popleft()
          table[x].popleft()
#          cur[i] += 1
#          cur[x] += 1
          game[i] = 1
          game[x] = 1
          flag = 1
#    if any() == 0:
#      print(count)
#      exit()
    if flag == 0:
#      print(-1)
      break
#  print(table)
#  print(any(table))
  if any(table):
    print(-1)
  else:
    print(count-1)  

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

now = []
for i in range(n):
    now.append(a[i].popleft()-1)
    a[i].append(0)
# print(a)
# print(now)

ans = 0
battle = 0
max_battle = n*(n-1)//2
while battle < max_battle:
    checked = [False]*n
    nogame = True
    for i in range(n):
        x = i
        y = now[i]
        if checked[i] or checked[y] or now[i]==-1:
            continue
        checked[i] = True
        if now[y]==i:
            checked[y] = True
            now[x] = a[x].popleft()-1
            now[y] = a[y].popleft()-1
            battle += 1
            nogame = False
            # print(i, now)

    if nogame:
        print(-1)
        exit()
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_dict = {}
for i in range(N):
  a_dict[i] = [int(a) -1 for a in input().split()]

ans = 0
while len(a_dict) > 0:
  flag = False
  entried = []
  for i  in range(N):
    if i in entried:
      continue
    if i in a_dict:
      i2 = a_dict[i][0]
      if a_dict[i2][0] == i and i not in entried and i2 not in entried:
        entried.extend([i,i2])
        del a_dict[i2][0], a_dict[i][0]
        if len(a_dict[i]) == 0: del a_dict[i]
        if len(a_dict[i2]) == 0: del a_dict[i2]
        flag = True
  if flag is False:break
  ans += 1
print(ans if len(a_dict) == 0 else -1)

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) and (finish[i] == 0):
      if (A[A[i][0] - 1][0] == i + 1) 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:
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.values():        
        for b in battle:
            next_A[b] = current_A[b][1:]
    return next_A

def make_battle_set(can_set):
    battle_set = collections.Counter()
    battle_players = set()
    index = 0
    for c in can_set:        
        if(c & battle_players == set()):
            battle_set[index] = c
            index += 1
            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:
# -*- 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

	anfl = True

	for i in range(100000):
		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:
			anfl = False
			break

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

		print(ans)
	else:
		print((N*(N-1))/2)



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[]]
for i in range(n):
  l1=list(map(int,input().split()))
  l.append(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())
import sys
input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[::-1]

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    for _ in range(10**9):
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]-1
            if  A[enemy][IDX[enemy]] == 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:
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 A[i] != [] and game_flag[i] == False:
            j = A[i][-1]
            if A[j] != [] and A[j][-1] == i and game_flag[j] == False:
                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:
N = int(input())
match_l = []
for _ in range(N):
    match_l.append(list(map(int,input().split())))

day = 0
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)

    day += 1

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [0] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already:
                continue
            if i in already:
                continue

            if i == next_pos[now] - 1:
                if end:
                    end = False
                if A[i]:
                    next_pos[i] = A[i].pop(0)
                else:
                    next_pos[i] = 0
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = 0
                al_add(i)
                al_add(now)
        ans += 1
        if end:
            ans = -1
            break
        if next_pos == check:
            break
    print(ans)
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:
      None
    else:
      B[i] = 1
      if dp[i] == n-1:
        None
      else:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          break
        else:
          if B[miru] != 1:
            sie = dp[miru]
            if L[miru][sie][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              act += 1
            else:
              None
          else:
              None
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>5000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def main():
    n = int(input())
    ls_ = [[int(x) for x in input().split()] for _ in range(n) ]
    ls = [deque(ls_[i]) for i in range(n)]


    can = [0 for _ in range(n)]


    for i in range(n):
        can[i] = ls[i].popleft()
    ans = 0
    while 1:
        if sum(can)==0:
            break
        flg = False
        for i in range(n):
            if can[i]==0:
                pass
            else:
                if can[can[i]-1]-1 ==i:
                    can[can[i]-1] = 0
                    can[i]=0
                    flg = True
        if flg == False:
            print(-1)
            exit()

        for i in range(n):
            if can[i]==0:
                if len(ls[i]) != 0:
                    can[i] = ls[i].popleft()
        ans += 1
    print(ans)

if __name__ =="__main__":
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[int(i) - 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 = {}
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_amount == N*(N-1)//2:
                print(days+1)
                exit(0)
        if games*2 >= N:
            break
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1

Submission status: Time Limit Exceeded

Solution code:
#e
n = int(input())
A = [[]] * (n+1)
for i in range(1,n+1):
    A[i] = list(map(int, input().split()))

day = 0
rest = n * (n-1) /2
flg = False
while rest != 0 and flg == False:
    day += 1
    play_in_date = 0
    in_play = [0]*(n+1)
    for i in range(1,n+1):
        if A[i]!=[] and A[A[i][0]]!=[] and A[A[i][0]][0] == i:
            p1, op = i, A[i][0]
            if in_play[p1] == 0 and in_play[op] == 0:
                in_play[p1] = 1
                in_play[op] = 1
                A[p1].remove(op)
                A[op].remove(p1)
                play_in_date += 1
                rest -= 1
                #print('day: ',day,' rest ',rest, ' p1: ',p1,'op: ',op)
    if play_in_date == 0:
        flg = True
if flg == True:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_dict = {}
for i in range(N):
  a_dict[i] = [int(a) -1 for a in input().split()]

ans = 0
while len(a_dict) > 0:
  flag = False
  entried = []
  for i  in range(N):
    if i in a_dict:
      i2 = a_dict[i][0]
      if a_dict[i2][0] == i and i not in entried and i2 not in entried:
        entried.extend([i,i2])
        del a_dict[i2][0], a_dict[i][0]
        if len(a_dict[i]) == 0: del a_dict[i]
        if len(a_dict[i2]) == 0: del a_dict[i2]
        flag = True
  if flag is False:break
  ans += 1
print(ans if len(a_dict) == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
*D, = open(0)
n = int(D[0])
data = []
for i in range(n):
    l = map(int, D[i+1].split())
    data.append([val-1 for val in l])
    
    
from collections import deque
table = []
for i in range(n):
    table.append(deque())
    for j in data[i]:
        if i > j:
            table[i].append('{},{}'.format(j,i))
        else:
            table[i].append('{},{}'.format(i,j))
        
        
cnt = 0
while True:
    candi = {}
    for i, que in enumerate(table):
        if que:
            if que[0] in candi:
                candi[que[0]].append(i)
            else:
                candi[que[0]] = [i]

    END = True
    for it in candi.values():
        if len(it)==2:
#             print(it)
            table[it[0]].popleft()
            table[it[1]].popleft()
            END = False
    if END:
#         print('end')
        break
    cnt += 1
    
INVALID = True
for it in table:
    if not it:
        INVALID = False
        break

if INVALID:
    print('-1')
else:
    print(cnt)

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)

first = a_list[:, 0]
target = n_index[first[first] == n_index]
a_index[target] += 1
ans = 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)

    cand = a_list[target, a_index[target]]
    target_index = (a_list[cand, a_index[cand]] == target)
    target = np.array(list(set(cand[target_index]) | set(target[target_index])))
    if len(target) == 0:
        break

    a_index[target] += 1
    ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [[int(x)-1 for x in input().split()] for _ in range(N)]
cnt = 0
g = [-1] * N
while(1):
    need_break = 1
    loop = 1
    for u in range(N):
        if (g[u] != -1): continue
        to_lst = A_list[u]
        if (len(to_lst) == 0): continue
        g[u] = to_lst.pop(0)
    for i, to in enumerate(g):
        need_break *= (to == -1)
        if (to != -1 and i == g[to]):
            g[i] = -1
            g[to] = -1
            loop = 0
    if (need_break):
        break
    if (loop):
        print(-1)
        exit()
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
fin = [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-1) if fin[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
            if deg[n] == N - 1:
                fin[n] = True
            if deg[op - 1] == N - 1:
                fin[op - 1] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
# ここから
import sys
from collections import deque
input = sys.stdin.readline

def resolve():
    n = int(input())
    orders = [list(map(int, input().split())) for _ in range(n)]
    match_order = []

    for i in range(n):
        match_sets = deque(map(lambda x: frozenset({i+1, x}), orders[i]))
        match_order.append(match_sets)

    count = 0

    while True:
        next_matches = [m[0] for m in match_order if len(m) > 0]
        today_matches = [x for x in set(next_matches) if next_matches.count(x) > 1]

        if len(today_matches) == 0:
            ls = [len(m) for m in match_order]
            if sum(ls) > 0:
                count = -1
            break

        for m in match_order:
            if len(m) > 0 and m[0] in today_matches:
                m.popleft()

        count += 1

    print(count)



resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

for _ in range(N):
	A.append(list(map(int, input().split())))
	

	
played_flg = 1
day = 0
played_game = 0

while played_flg:
	played_flg = 0
	day += 1
	game_played = [False for _ in range(N)]
	for i in range(N):
		# print(game_played)
		if len(A[i]) != 0 and A[A[i][0] - 1][0] - 1 == i: 
			if game_played[A[i][0] - 1] == False:
				if game_played[i] == False:
					# print(i, A[i][0] - 1)
					game_played[A[i][0] - 1], game_played[i] = True, True
					played_flg = 1
					played_game += 1
					A[A[i][0] - 1].pop(0)
					A[i].pop(0)
	if played_game == N * (N - 1) / 2:
		break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[0 for i in range(a)]
  while sum(len(v) for v in b)!=0:
    f=[0 for i in range(a)]
    ans+=1
    T=0
    for i in range(a):
      if d[i]==1 or f[i]==1 or len(b[i])==0:
        continue
      else:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          d[i]=0
          d[e]=0
          f[i]=1
          f[e]=1
        else:
          c[e].append(i)
          d[i]=1
    if T==0:
      print(-1)
      exit()
      
      
  print(ans)  
if __name__ == '__main__':  
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():    
    n = int(input())
    a = [list(reversed(list(map(int,input().split())))) for _ in range(n)]
    ans = 0
    c = 0
    nn = n*(n-1)//2
    rng = range(n)
    for _ in range(nn):
        pop_list = []
        pap = pop_list.append
        for i in rng:
            for j in range(i+1,n):
                if a[i] and a[j]:
                    if a[i][-1]-1 == j and a[j][-1]-1 == i:
                        pap(i)
                        pap(j)
                        break
        if not pop_list:
            ans = -1
            break
        for i in pop_list:
            _ = a[i].pop(-1)
        c += len(pop_list)//2
        ans += 1
        if c == nn:
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# A,B = list(map(int, input().split()))
N = int(input())

A_mat = np.zeros((N, N-1), dtype = np.int)
# print(A_mat)

for i in range(N):
    A_mat[i] = list(map(int, input().split()))
    # print(A_mat)
A_mat -= 1
# print(A_mat)
total_games = N * (N-1) // 2

days = 1

current_As = A_mat[:,0]
current_As_index = np.zeros((N),dtype = np.int)

already_played = []

# print(current_As)
games = 0
while True:
    todays_game = 0
    for i in range(N):
        opponent_index = current_As[i]
        if i in already_played or opponent_index in already_played:
            continue
        # print("i : {}, opponent_index : {}".format(i, opponent_index))
        if current_As[opponent_index] == i:
            current_As_index[i]+=1
            if current_As_index[i] < N-1:
                current_As[i] = A_mat[i, current_As_index[i]]

            current_As_index[opponent_index]+=1
            if current_As_index[opponent_index] < N-1:
                current_As[opponent_index] = A_mat[opponent_index, current_As_index[opponent_index]]

            games += 1
            todays_game += 1
            already_played += [i, opponent_index]
    if todays_game == 0:
        print("-1")
        exit()
    if games == total_games:
        print(days)
        exit()
    days += 1
    already_played = []
    # print()
    # print(current_As)
    # print(games)
    # print(days)
    # input("...")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
league = []
match = {}
ll = []
for i in range(n):
    league.append(list(map(int, input().split())))
    match[i+1] = league[i][-1]
    ll.append(n-3)
ans = 0
cnt = 0
while cnt < n:
    tmp = []
    for k,v in match.items():
        if v in match and match[v] == k:
            tmp.append(v)
    if not tmp:
        print(-1)
        exit()
    for i in tmp:
        if ll[i-1] < 0:
            cnt += 1
            match[i] = 0
        else:
            match[i] = league[i-1][ll[i-1]]
            ll[i-1] -= 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        q = collections.deque(map(int, input().split()))
        Q.append(q)

    games = N*(N-1)//2
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            j = Q[i][0] - 1
            if len(Q[j]) != 0 and gamed[j] == 0:
                if Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    gamed[i] = 1
                    gamed[j] = 1
                    games -= 1
                    continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>10000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

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