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
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
now=[[0,0] for i in range(n)]
day=0

while 1:
    day+=1
    siaisuu=0
    for i in range(n):
        if now[i][0]==n-1 or now[i][1] == day:
            continue
        nex=a[i][now[i][0]]
        if i+1==a[nex-1][now[nex-1][0]] and now[nex-1][1] != day:
            siaisuu+=1
            now[i][0]+=1
            now[i][1],now[nex-1][1]=day,day
            now[nex-1][0]+=1
    if siaisuu==0:
        break

for i in range(n):
    if now[i][0]!=n-1:
        print(-1)
        quit()

print(day-1)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    while any([loc_i != -1 for loc_i in loc]):  # TODO: infinity handling
        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()

Submission status: Time Limit Exceeded

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

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


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

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0
for i in range(N * (N-1) // 2):
    current = a_list[n_index, a_index]
    update = current[current] == n_index
    a_index[update] += 1

    if np.all(np.logical_not(update)):
        break
    else:
        ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
# e
# 4
# 2 3 4
# 1 3 4
# 4 1 2
# 3 1 2
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
game = [0]*n
day = [0]*n
cnt = 0
pre = 0
M = n*(n-1)//2
ok = True
while cnt < M:
    for i in range(n):
        if cnt == M:
            break
        if game[i] != n-1:
            opp = a[i][game[i]]-1
            if a[opp][game[opp]]-1 == i:
                cnt += 1
                game[i] += 1
                game[opp] += 1
                mday = max(day[i]+1, day[opp]+1)
                day[i] = day[opp] = mday
                continue
    if cnt == pre:
        ok = False
        cnt = M
    else:
        pre = cnt
if ok:
    print(max(day))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

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

ans = 0
cnt = 0
M = N * (N - 1) // 2
while cnt < M:
  tmp = cnt
  q = [i for i in range(N)]
  while len(q) > 0:
    p = q.pop(0)
    if len(A[p]) == 0:
      continue
    if A[A[p][0]][0] == p and A[p][0] in q:
      q.remove(A[p][0])
      A[A[p][0]].pop(0)
      A[p].pop(0)
      cnt += 1
  if tmp == cnt:
    ans = -1
    break
  else:
    ans += 1
print(ans)

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()))
  l1=l1[::-1]
  l[i+1]=l1
b=True
day=0
while b and not(l==[[] for i in range(n+1)]):
  day+=1
  todaygame=[1 for i in range(n+1)]
  for i in range(1,n+1):
    if l[i]==[]:
      pass
    elif l[l[i][-1]]==[]:
      pass
    elif l[l[i][-1]][-1]==i:
      if todaygame[i]==1  and todaygame[l[i][-1]]==1:
        todaygame[i]=0
        todaygame[l[i][-1]]=0
        del l[l[i][-1]][-1]
        del l[i][-1]
  if set(todaygame)==[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] + list(reversed(list(map(int, input().split())))) for _ in range(N)]
ans, match = 0, 0
while match < N * (N - 1) // 2:
    ans, pair = ans + 1, []
    for i in range(N):
        if A[A[i][-1] - 1][-1] == i + 1 and not {i + 1, A[i][-1]} in pair:
            pair.append({i + 1, A[i][-1]})
            match += 1
    for p in pair:
        for pi in p:
            A[pi - 1].pop()
    if len(pair) == 0:
        print(-1)
        exit()

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())))

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[0]*n
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1 and q[a[i][0]-1]==0 and q[i]==0:
            q[a[i][0]-1]+=1
            q[i]+=1
            
            a[a[i][0]-1].pop(0)
            a[i].pop(0)
            
            #q.append(i)
            #q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    #if len(q)>0:
        #for k in q:
            #a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    a = [list(map(int, input().split())) for _ in range(n)]
    j = [0] * n
    all_g = n * (n - 1) // 2
    g = 0
    d = 0
    while 1:
        d += 1
        finish = set()
        for i in range(n):
            if i in finish: continue
            if j[i] == n-1: continue
            ii = a[i][j[i]] - 1
            if a[ii][j[ii]] - 1 == i:
                g += 1
                finish.add(ii)
                finish.add(i)
        if g == all_g:
            print(d)
            break
        if not finish:
            print(-1)
            break
        for ii in finish:
            j[ii]+=1

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) - 1 for a in input().split()] for _ in range(N)]

    #print(A)
    day = 0
    match = [0 for i in range(N)]

    #print(match)
    while True:
        onmatch = set()
        for i in range(N):
            if i not in onmatch and match[i] < N - 1:
                vs = A[i][match[i]]
                if match[vs] < N - 1:
                    if A[vs][match[vs]] == i and vs not in onmatch:
                        onmatch |= {i, vs}
                        match[i] += 1
                        match[vs] += 1
        if onmatch: day += 1
        else: break
    #print(match)

    for i in match[:N]:
        if i < N - 1:
            print(-1)
            break
    else: print(day)

    return 0

if __name__ == "__main__": solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
next_pos = [A[i].pop(0) for i in range(N)]
ans = 0
check = [0 for _ in range(N)]
while True:
    end = True
    if next_pos == check:
        break
    already = set()
    for i in range(N):
        now = next_pos[i] - 1
        if now == -1:
            continue
        if now in already or 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
            already.add(i)
            already.add(now)
    ans += 1
    if end:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])

ans = 0
while (True):
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i][0]
      if aite not in tmpset and dic[aite][0] == i:
        dic[i].popleft()
        dic[aite].popleft()
        tmpset.add(i)
        tmpset.add(aite)
        playcount += 1
  if playcount > 0:
    ans += 1
  if playcount == 0:
    break
failedflag = False
for i in range(1, N+1):
  if len(dic[i]) > 0:
    failedflag = True
if failedflag:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def main():
  inp = sys.stdin.readline
  n = int(inp())
  target_num = n*(n-1)//2

  all_set = set()
  fin = set()
  all_add = all_set.add
  a = [None] * n
  for i in range(n):
    a[i] = deque(map(int, inp().split()))
  ans = 0

  while True:
    cur_set = set()
    flag = False
    for i in range(n):
      if len(a[i]):
        tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
        if a[i][0] in fin:
          flag = False
          break
      else:
        fin.add(i+1)
        continue
      if tup not in cur_set:
        cur_set.add(tup)
      elif tup in cur_set:
        all_add(tup)
        t1, t2 = tup
        a[t1-1].popleft()
        a[t2-1].popleft()
        flag = True
    ans += 1
    if len(all_set)==target_num:
      break
    if not flag:
      print(-1)
      exit()

  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

N = int(input())
table = [list(map(int, input().split())) for i in range(N)]
count = 0
while True:
  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 table[x][0] == i+1 and game[x] == 0:
#        print(count,i,x)
        table[i].pop(0)
        table[x].pop(0)
        game[i] = 1
        game[x] = 1
        flag = 1
  if any(table) == 0:
    print(count)
    exit()
  if flag == 0:
    print(-1)
    exit()
print(count)

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)
while(True):  
  answer+=1
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if len(amat[i]) == 0 or matched_flag[i]:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      amat[i].pop()
      amat[ai_next].pop()
      matched_flag[i]=True
      matched_flag[ai_next]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    maxlist=-1
    for i in range(1,N+1):
      maxlist=max(maxlist,len(amat[i]))
    if maxlist==0:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=deque([deque([int(_)-1 for _ in input().split()]) for __ in range(n)])
f=[0 for _ in range(n)]
ff=0
m=n*(n-1)//2
d=0
while True:
    for i in range(n):
        if a[i] != deque([]):
            k=a[i][0]
            if f[i]==0 and f[k]==0:
                if a[k][0]==i:
                    f[i]=1
                    f[k]=1
                    m-=1
                    a[k].popleft()
                    a[i].popleft()
                    ff=1
    if ff:
        f=[0 for _ in range(n)]
        d+=1
        ff=0
        if m==0:
            print(d)
            break
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
target_num = n*(n-1)//2

all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0

while True:
  cur_set = set()
  flag = False
  for i in range(n):
    if len(a[i]):
      tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
    else:
      continue
    if tup not in cur_set:
      cur_set.add(tup)
    elif tup in cur_set:
      all_set.add(tup)
      t1, t2 = tup
      a[t1-1].popleft()
      a[t2-1].popleft()
      flag = True
  ans += 1
  if len(all_set)==target_num:
    break
  if not flag:
    print(-1)
    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  l=[]
  for _ in range(n):
    _l=LI()
    _l.reverse()
    l.append(_l)

  c=n*(n-1)
  ans=1
  nagasa=[n-1]*n
  while True:
    m=[0]*n
    _c=c

    for i in range(n):
      if c<=0:
        return ans

      if m[i]!=0:
        continue

      if nagasa[i]!=0:
        a=l[i][-1]-1

        if nagasa[a]!=0:
          if l[a][-1]==i+1:
            if m[a]==0 and m[i]==0:
              l[a].pop()
              l[i].pop()
              m[a]=1
              m[i]=1
              nagasa[a]-=1
              nagasa[i]-=1
            else:
              continue
            c-=2
          else:
            continue
        else:
          return -1
      else:
        continue
    if _c==c:
      return -1
    ans+=1

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
#

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

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

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

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

            if agrid[target][agrid_pointer[target]] != 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:
from collections import deque
n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

while (num < n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit = visit.union({a_list[k].popleft(), a_list[j].popleft()})                                                
    if (len(visit) == 0):
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
ans = 0
while True:
    skip_list = set()
    for i, n in enumerate(A):
        if i in skip_list or len(n) == 0 or len(A[n[0]]) == 0 or n[0] in skip_list:
            continue
        if A[n[0]][0] == i:
            skip_list.add(A[n[0]].pop(0))
            skip_list.add(n.pop(0))
    if len(skip_list) == 0:
        print(-1)
        exit()
    ans += 1
    if len(list(filter(lambda x: len(x) == 0, A))) == N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from collections import deque

def main():
    N = II()
    a_mat = []
    for i in range(N):
        a_mat.append(deque(LI()))

    cnt = 0
    first_list = [a_list.popleft() for a_list in a_mat]
    while True:
        # この日に試合できる可能性リスト
        # 試合する人リスト
        match_list = []
        for i, a in enumerate(first_list):
            ind = i+1
            # 試合をするペアの要素を入れていく
            if first_list[a-1] == ind:
                match_list.append(i)

        if len(match_list) == 0:
            print(-1)
            return

        # 試合をしたことを反映
        for i in match_list:
            if len(a_mat[i]) == 0:
                first_list[i] = 0
            else:
                first_list[i] = a_mat[i].popleft()

        # 一日経過
        cnt += 1

        # 終了判定
        if sum(first_list) == 0:
            break

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy
# Your code here!
n=int(input().rstrip())
a=[]

cnt=[]
for i in range(n):
    cnt.append(0)
    a.append(input().rstrip().split(" "))
    for j in range(n-1):
        a[i][j]=int(a[i][j])
ans=0
day=0
last=int(n*(n-1)/2)


while(not last==0):
    olast=last
    day=day+1
    for i in range(n):
        cnt[i]=0
    for i in range(n):
        if(cnt[i]==1 or len(a[i])==0):
            continue
        else:
            s=a[i][0]
            if(len(a[s-1])==0 or cnt[s-1]==1):
                continue
            if( i+1==a[s-1][0] and s==a[i][0]  ):
                cnt[i]=1
                cnt[s-1]=1
                last=last-1
                del a[i][0]
                del a[s-1][0]
    #print(a)
    #print(last)
    if(last==olast):
        day=-1
        break
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
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:
    ok = [True] * N
    for i in range(1,N+1):
        if A[i] and ok[i-1]:
            t = A[i][0]
            if A[t] and i == A[t][0] and ok[i-1] and ok[t-1]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                ok[i-1] = False
                ok[t-1] = False
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

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

print(result)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

    # print (check)
    # for i in check:
    #     if i != N - 1:
    #         print (-1)
    #         exit()

    print (-1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

# グラフつくる
graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

# トポロジカルソート
S = []
for v in range(N ** 2):
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != N ** 2:
    print(-1)
    exit()


@lru_cache(maxsize=None)
def dfs(v):
    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)
# DAG の最長パスが答え

Submission status: Time Limit Exceeded

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

a = 0

cc = 0

ccc = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです
m = (N*(N-1))//2
for i in range(m):#周回
  btlf = [False for i in range(N)]#リセット
  ccc = 0
  for j in range(N):
    #print(idx)
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if a>j:
        if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
          idx[a-1]+=1
          btlf[a-1] = True
          idx[j]+=1
          btlf[j] = True
          cc+=1
          ccc+=1
  if cc == m:#idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if ccc == 0:#対戦が一度もなければ打ち切ります
    break
if f:
  print(-1)

Submission status: Time Limit Exceeded

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

days = 0

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
next_pos = [A[i].pop(0) for i in range(N)]
ans = 0
check = [0 for _ in range(N)]
while True:
    cnt = 0
    if next_pos == check:
        break
    already = set()
    for i in range(N):
        now = next_pos[i] - 1
        if now == -1:
            continue
        if now in already or i in already:
            continue
        if i == next_pos[now] - 1:
            cnt += 1
            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
            already.add(i)
            already.add(now)
    ans += 1
    if not cnt:
        ans = -1
        break
print(ans)