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

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

else:
    N = _I()
    for i in range(N):
        A_list.append(LI())
    #  perr(A_list)
new_A_list = []
for A in A_list:
    new_A_list.append([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 = [0 for i in range(N)]
done_player_list = []
position_sum = 0
done_sum = (N-1)*N
while True:
    #  print('day: ', current_day)
    #  print('current position list', current_position_list)
    #  pdb.set_trace()
    is_ok = False
    #  if all(position == N-1 for position in current_position_list):
    if position_sum == done_sum:
        # 全試合終了
        break

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

        if current_position_list[i] == N - 1:
            # この選手はすべての試合を終了している
            continue

        # iの試合相手のidx
        opponent_idx = A_list[i][current_position_list[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.append(opponent_idx)
            done_player_list.append(i)
            current_position_list[i] += 1
            current_position_list[opponent_idx] += 1
            position_sum += 2
            # 試合がまだ可能であるというフラグをつける
            is_ok = True

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

    done_player_list = []
    current_day += 1

print(current_day)

Submission status: Time Limit Exceeded

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- 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 update.sum() == 0:
        break
    else:
        ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

league = [ [ int(v)-1 for v in input().split() ] for i in range(n) ]
done = [ 0 for i in range(n) ]

def day():
    day_match = 0
    match = [ 0 for i in range(n) ]
    for i in range(n):
        if match[i] == 0:
            j = league[i][done[i]]
            if i != j and league[j][done[j]] == i and match[j]== 0:
                league[i][done[i]] = i
                league[j][done[j]] = j
                match[i] = 1
                match[j] = 1
                day_match += 1
                if done[i] < n-2:
                    done[i] += 1
                if done[j] < n-2:
                    done[j] += 1
    return day_match

cal_match = (n*n-n) // 2
total_match = 0
cont = 1
d = 0
while cont:
    d += 1
    one_day_match = day()
    total_match += one_day_match

    if one_day_match == 0:
        cont = 0
        print(-1)
    elif total_match == cal_match:
        cont = 0
        print(d)

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 = []
    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.append(A[n[0]].pop(0))
            skip_list.append(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:
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    day = -1

    while True:
        day += 1
        g = Graph(N)
        flag = False

        for i, h in enumerate(a_head):
            if h == N-1:
                continue
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[0,0]
while count!=n*(n-1)//2:
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check[0]=check[1]
  check[1]=count
  if check[0]==check[1]:
    print(-1)
    sys.exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
def p_e():
    N = int(input())
    A = [list(map(lambda x: x - 1, map(int, input().split()))) for _ in range(N)]

    ans = 0
    while True:
        idx = []
        for i in range(N):
            if not A[i]:
                continue

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

        if not idx:
            break

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

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

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)

        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)

        # print(hashmap)

        cnt = 0
        old_cnt = 0
        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in range(N):
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))

            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1

            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt

if __name__ == '__main__':
    Solution().main()

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:
          continue
      else:
        continue
    if _c==c:
      return -1
    ans+=1

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

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

game_count = [0 for _ in range(n)]
ans = 0
remaining_games = n * (n-1) //2
last_remains = remaining_games
while(remaining_games>0):
    done = [False for _ in range(n)]
    for playeri in range(n):
        if game_count[playeri] >= n-1:
            done[playeri] = True
            continue

        # print(f'day:{ans} p:{playeri} games:{game_count[playeri]} done:{done[playeri]} ', end='')

        rival = a[playeri][game_count[playeri]]
        if done[playeri] or done[rival]:
            print()
            continue

        # print(f'rival:{rival}')
        if a[rival][game_count[rival]] == playeri: #match
            game_count[playeri] += 1
            game_count[rival] += 1
            done[playeri] = True
            done[rival] = True
            remaining_games -= 1
    ans += 1
    if last_remains == remaining_games:
        print(-1)
        break
else:
    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):
        a = list(map(int, input().split()))
        q = collections.deque()
        for i in a:
            q.append(i)
        Q.append(q)
    days = 0
    while True:
        if all(len(q) == 0 for q in Q):
            break
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            game = False
            for j in range(i+1, len(Q)):
                if len(Q[j]) == 0 or gamed[j] != 0:
                    continue
                if Q[i][0] == j+1 and 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
                    break
            if game:
                break
        days += 1
        if not b:
            print(-1)
            return
    print(days)
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({k, j})
                        a_list[k].popleft()
                        a_list[j].popleft()
    if (len(visit) == 0):
        day = -1
        break
print(day)

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:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
cnt_max = {}
for i in range(n):
    cnt_max[i] = 0
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    flag = False
    for i in range(n)[::-1]:
        if memo[i] == len(a[0]):
            continue
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            flag = True
            tmp = memo[i]
            max_1 = max(cnt_max[i], cnt_max[a[i][tmp] - 1])
            cnt_max[i] = max_1 + 1
            cnt_max[a[i][tmp] - 1] = max_1 + 1
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
ans = 0
for i in cnt_max:
    ans = max(cnt_max[i] , ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
B = [0]*N
S = 0
ans = 0
while True:
    C = [0]*N
    k=1
    while k!=0:
        k = 0
        for n in range(N):
            if C[n]==0 and B[n]!=N-1:
                b = A[n][B[n]]
                if C[b]==1:continue
                if A[b][B[b]]==n:
                    B[n]+=1
                    B[b]+=1
                    C[n]=1
                    C[b]=1
                    k=1
    if sum(C)==0:break
    ans +=1
print(ans if sum(B)==N*(N-1) else -1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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

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

#print(A)

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

n1n = n*(n-1)

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

Submission status: Time Limit Exceeded

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

day = 0
while(True):
    day += 1
    v = list(range(N))
    # その日まだ試合していない人のリスト
    for p in range(N):
        if len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if p in v  and  q in v  and  A[q][0]-1 == p:
            #print(day, p, q, v, A)
            v.remove(p)
            v.remove(q)
            del A[p][0]
            del A[q][0]
        
    flag = 0
    for i in range(N):
        if len(A[i]) > 0:
            flag = 1
    if flag == 0:
        print(day)
        break
        
    if len(v) == N:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [deque() for _ in range(N + 1)]
for i in range(1, N + 1):
    for e in map(int, input().split()):
        A[i].append(e)

day = [1 for _ in range(N + 1)]
empty_queues = 0
while empty_queues < N:
    matched = False
    for i in range(1, N + 1):
        if len(A[i]) == 0:
            continue
        competitor = A[i].popleft()
        cp = A[competitor].popleft()
        if cp == i:
            matched = True
            date = max(day[i], day[competitor]) + 1
            day[i] = date
            day[competitor] = date
            if len(A[i]) == 0:
                empty_queues += 1
            if len(A[competitor]) == 0:
                empty_queues += 1
        else:
            A[i].appendleft(competitor)
            A[competitor].appendleft(cp)
    if not matched:
        print(-1)
        exit(0)
print(max(day[1:]) - 1)

Submission status: Time Limit Exceeded

Solution code:
# ABC139
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = deque(A[x : x + N - 1])
    ans, flg, matched = 0, 0, set()
    while B:
        for i in list(B.keys()):
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    flg = 1
                    if not B[i]:
                        del B[i]
                    if not B[x]:
                        del B[x]
        if flg:
            ans += 1
            flg, matched = 0, set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: N-a, As))))
  A.append(As)
A.reverse()
#print(A)
d = 0
n = 0
while True:
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if j < i:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      gs.append((i, j))
  if gs == []:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  for i, j in gs:
    A[i].pop()
    A[j].pop()
  d += 1
print(d)

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):
            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
def main():
    N=int(input())
    A=[[]]
    for _ in range(N):
        A.append(deque(map(int, input().split())))

    days = 0
    changed = True
    while changed:
        played=[]
        changed = False
        for i in range(1,N+1):
            if len(A[i]) == 0:
                continue
            a1 = A[i][0]
            if a1 in played:
                continue
            if len(A[a1]) == 0:
                continue
            a2 = A[a1][0]
            if a2 in played:
                continue
            if a2 == i:
                A[i].popleft()
                A[a1].popleft()
                played.append(i)
                played.append(a1)
                changed = True
        if changed:
            days+=1

    for a in A:
        if len(a) > 0:
            print(-1)
            break
    else:
        print(days)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def notempty(b):
    return any(map(lambda x: len(x), b))


n = int(input())
a = [list(reversed(list(map(lambda x:int(x) - 1, input().split()))))
     for _ in range(n)]
cnt = 0
while notempty(a):
    flg = 0
    cnt += 1
    li = [True] * n
    for i in range(n):
        if not len(a[i]):
            continue
        tmp = a[i][-1]
        if li[i] and len(a[tmp]) and li[tmp] and a[tmp][-1] == i:
            a[i].pop()
            a[tmp].pop()
            li[i], li[tmp] = False, False
            flg = 1
    if not flg:
        print(-1)
        exit(0)
print(cnt)

Submission status: Time Limit Exceeded

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

idx = [0] * N

cnt = 0
ans = -1
q = list(range(N))
for day in range(N * (N - 1) // 2 + 1):
    # print("#", q, idx)
    if len(q) == 0: break
    elif cnt == (N * (N - 1) // 2):
        ans = day
        break
    #
    used = [False] * N
    q_tmp = []
    for src in q:
        if used[src] or (idx[src] >= N - 1): continue
        dst = A[src][idx[src]] - 1
        if used[dst] or (idx[dst] >= N - 1): continue
        #
        if A[dst][idx[dst]] - 1 == src:
            # print("##", src, dst)
            idx[src] += 1
            used[src] = True
            q_tmp.append(src)
            idx[dst] += 1
            used[dst] = True
            q_tmp.append(dst)
            cnt += 1
    q = list(q_tmp)
            
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

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

    cnt = 0
    first_list = [a_list.pop() 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].pop()

        # 一日経過
        cnt += 1

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

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
day = 0
match = [0 for i in range(n)]
while match != [n - 1 for i in range(n)]:
    add = [False for i in range(n)]
    for i in range(n):
        if match[i] <= n - 2:
            j = a[i][match[i]] - 1
            if a[j][match[j]] - 1 == i:
                add[i] = True
                add[j] = True
    if add != [False for i in range(n)]:
        match = [match[i] + int(add[i]) for i in range(n)]
        day += 1
    else:
        break
else:
    print(day)
    sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [[0 for j in range(n-1)] for i in range(n)]
for i in range(n):
  tmp  = list(map(int, input().split()))
  for j in range(n-1):
    a[i][j] = tmp[j]

cnt = 0
day = 0
done = []
while cnt < n * (n-1) / 2:
  day += 1
  flg = 0
  done.clear()
  
  for i in range(n):
    if len(a[i]) > 0:
      if len(a[a[i][0]-1]) > 0 and a[i][0]-1 > i:
#        print('DEBUG HIT '+str(i)+':'+str(a[i][0])+':'+str(a[a[i][0]-1][0]))
        if a[a[i][0]-1][0]-1 == i:
          done.append(i)
          done.append(a[i][0]-1)
          flg = 1
          cnt += 1

  if flg == 0:
    day = -1
    break
  else:
    while(len(done) != 0):
      del a[done.pop(0)][0]
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from queue import Queue

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

match = [0 for i in range((n*(n-1))//2)]
child = [[] for i in range((n*(n-1))//2)]
isroot = [True for i in range((n*(n-1))//2)]


def bfs(root):
    q = Queue()
    q.put(root)
    match[root] = 1
    while(not q.empty()):
        item = q.get()
        # print(q, item)
        for ch in child[item]:
            # print(ch)
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                q.put(ch)




for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i,j)
        iii, k = min(i, k), max(i,k)
        idx1 = ((j-1)*(j-2))//2 + (ii-1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        isroot[idx2] = False
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# sys.exit()

for idx, flag in enumerate(isroot):
    if flag:
        bfs(idx)
ans = 1
for m in match:
    if m > ans:
        ans = m
    if m == 0:
        print(-1)
        sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
league=[]
for _ in range(n):
    a=deque(map(int,input().split()))
    league.append(a)

total_match=n*(n-1)//2
match=0
day=0

while match<total_match:
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][0]-1
            if m in today_match:
                continue
            if league[m] and league[m][0]-1==i:
                today_match.extend((league[i].popleft()-1, league[m].popleft()-1))
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2

print(day)