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)

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

    else:
        N = _I()
        for i in range(N):
            A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx, A in enumerate(A_list):
        new_A_list[aidx] = tuple(i-1 for i in A)
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = {i:0 for i in range(N)}
    done_player_list = set()
    position_sum = 0
    done_sum = (N-1)*N
    #  all_done_players = set()
    for _ in range(10**9):
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

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

            #  if i in all_done_players:
            if current_position_list.get(i) == N-1:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list.get(i)[current_position_list.get(i)]
            if opponent_idx in done_player_list:
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list[opponent_idx][current_position_list[opponent_idx]] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                #  done_player_list += (opponent_idx, i)
                done_player_list.add(i)
                done_player_list.add(opponent_idx)
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                #  if current_position_list[i] == N-1:
                #      all_done_players.add(i)
                #  if current_position_list[opponent_idx] == N-1:
                #      all_done_players.add(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

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

        done_player_list = set()
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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

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

#print(A)

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

n1n = n*(n-1)
nm2 = n - 2
nm1 = n - 1
maxga = n//2

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

Submission status: Time Limit Exceeded

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

def main():
	n = int(input().strip())
	dqlist = [deque([-1])]
	for _ in range(n):
		v = list(map(int, input().strip().split()))
		dqlist.append(deque(v))
	day = 0
	zeroc = 0
	while True:
		picked = [0] * (n+1)
		changed = False
		for i in range(1, n+1):
			if picked[i] == 1:
				continue
			if len(dqlist[i]) == 0:
				continue
			if dqlist[dqlist[i][0]][0] == i:
				if picked[dqlist[i][0]] == 1:
					continue
				# OK
				changed = True
				c = dqlist[i].popleft()
				dqlist[c].popleft()
				picked[i] = 1
				picked[c] = 1
				if len(dqlist[i]) == 0:
					zeroc += 1
				if len(dqlist[c]) == 0:
					zeroc += 1
		if changed == False:
			if zeroc == n:
				print(day)
				return
			else:
				print(-1)
				return
		day += 1

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n = int(input())
game = [0]

for _ in range(n):
    comp = deque((map(int, input().split())))
    game.append(comp)

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == deque([]):
            continue

        you = game[me][0]
        if you in finish or game[you] == deque([]):
            continue
        else:
            if game[you][0] == me:
                finish.add(game[you].popleft())
                finish.add(game[me].popleft())
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Submission status: Time Limit Exceeded

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

td = []
ans = 0
skip = 0
execflg = False
while 1:
        for idx, val in enumerate(A):
                if not val:
                        skip += 1
                        continue
                oppidx = val[0] - 1
                opp = A[oppidx][0]
                if idx in td or oppidx in td:
                        continue
                
                if opp == idx + 1:
                        execflg = True
                        A[idx].pop(0)
                        A[oppidx].pop(0)
                        td.append(idx)
                        td.append(oppidx)
                if len(td) == N:
                        break
        else:
                if execflg:
                        td=[]
                        ans += 1
                        execflg = False
                        skip = 0
                else:
                        if skip == N:
                                print(ans)
                        else:
                                print(-1)
                        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
n=int(input())
a=[]
hd=[0]*n
for i in range(n):
    a.append(tuple(map(int,input().split())))
d=defaultdict(int)
for i in range(n):
    for j in range(n-1):
        d[(i,j)]=a[i][j]
loop=0
flag=0
while(flag<n):
    stk=[]
    for i in range(n):
        if hd[i]==n-1:
            continue
        idx=d[(i,hd[i])]-1
        if hd[idx]==n-1:
            print(-1)
            sys.exit()
        if d[(idx,hd[idx])]==i+1:
            stk.append(i)
    if not stk:
        loop=-2
        break
    for j in stk:
        hd[j]+=1
        if hd[j]==n-2:
            flag+=1
    loop+=1
print(loop+1)

Submission status: Time Limit Exceeded

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

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 > j:
                    if k not in visit:
                        if a_list[k][0] == j:
                            num += 1
                            visit.add(a_list[j].popleft())
                            visit.add(a_list[k].popleft())
    if ((j == n - 1) & (len(visit) == 0)):
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
player = []
for i in range(n):
    line = [int(x)-1 for x in input().split()]
    player.append(line)
    
done = [0 for _ in range(n)]

def check_finish():
    for d in done:
        if d != (n-1):
            return False
    return True
  
count = 0
ok_flg = False

while True:
    if check_finish():
        ok_flg = True
        break
    play_list = []
    for i in range(n):
        if (not i in play_list) and (not done[i] == (n-1)):
            p1 = i
            p2 = player[p1][done[i]]
            if p1 == player[p2][done[p2]]:
                play_list.append(p1)
                play_list.append(p2)
    if play_list == []:
        break
    for play_num in play_list:
        done[play_num] += 1
    count += 1

if ok_flg:
    print(count)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    for _ in range(N):
        A.append(list(map(int,input().split())))
    # next_pos = [A[i].pop(0) for i in range(N)]
    next_pos = []
    for i in range(N):
        next_pos.append(A[i].pop(0))
    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:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count, more_play):
    count = 0
#    roop_count = 0##########
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if more_play[i] and already_played[i] == 0: # 10**3
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if len(A_lst[p1]) == 0:
                        more_play[p1] = False
                    if len(A_lst[p2]) == 0:
                        more_play[p2] = False
#                    if roop_count > 10**4:########
#                        return -1#########
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)
more_play = [True]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count, more_play)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    N = int(input())
    A = []
    for i in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        row = [r - 1 for r in row]
        A.append(row)

    counter = [0] * (N + 1)
    finish = 0

    ans = 0
    s = set(range(N))
    done_s = set()
    while finish < N * (N - 1) // 2:
        checked = set()
        ans += 1

        exit_flg = True
        for n in s - done_s:
            # ある日程ですでにnは戦っている
            if n in checked:
                continue

            # nの対戦は終了
            if counter[n] == N - 1:
                continue

            checked.add(n)

            n_match = A[n][counter[n]]  # nの対戦相手
            n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相手

            # nの対戦相手はある日の試合をすでに終えている
            if n_match in checked:
                continue

            # マッチング成立
            if n == n_match_match:
                exit_flg = False

                checked.add(n_match)

                finish += 1
                counter[n] += 1
                counter[n_match] += 1

                if counter[n] == N - 1:
                    done_s.add(n)
                if counter[n_match] == N - 1:
                    done_s.add(n_match)

        # 一つも組み合わせられなかった
        if exit_flg:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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
allpc = 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
        allpc += 1
  if playcount > 0:
    ans += 1
  else:
    break
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

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 a<i:
          continue

        if m[a]!=0:
          continue

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

    if _c==c:
      return -1

    ans+=1

# main()
print(main())

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, to_lst in enumerate(A_list):
        if (g[u] != -1 or len(to_lst) == 0): continue
        g[u] = to_lst.pop(0)
    for i, to in enumerate(g):
        need_break *= int(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 numpy as np

n = int(input())
A = np.array([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 = np.zeros(n, dtype="int")
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
nm2 = n - 2
nm1 = n - 1
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = np.zeros(n, dtype="int")
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= nm2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == nm1 or ga == maxga:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
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

do   = []
done = []
for i in range(n):
  do.append(i)

while cnt < n * (n-1) / 2:
  day += 1
  flg = 0
  
  for i in do:
    if len(a[i]) > 0:
      if len(a[a[i][0]-1]) > 0 and (a[i][0] - 1) not in done:
#        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:
    do.clear
    while(len(done) != 0):
      tmp = done.pop(0)
      do.append(tmp)
      del a[tmp][0]
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


match2rank = dict()
ij2num = dict()
i2queue = [[]]
for i in range(n):
  i2queue.append(list())
  for num in map(int, input().split()):
    i2queue[i].append(num - 1)


cnt = 0
while True:
  used = set()
  for i, q1 in enumerate(i2queue):
    if not q1: continue
    n1 = q1[0]
    n2 = i2queue[n1][0]

    if (n2 == i) and n1 not in used and n2 not in used:
      used.add(q1.pop(0))
      used.add(i2queue[n1].pop(0))
  if not used:
    break
  cnt += 1

for q in i2queue:
  if q:
    print(-1)
    break
else:
  print(cnt)

Submission status: Time Limit Exceeded

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

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:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  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:
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
def dec(s):
  n = int(s)
  return n - 1

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

Q = [i for i in range(N)]
ans = 0
cnt = 0
M = N * (N - 1) // 2
while cnt < M:
  tmp = cnt
  q = Q.copy()
  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:
from collections import defaultdict, deque
outs = defaultdict(list)
ins = defaultdict(int)

def get_ab(h):
    return h // 10000, h % 10000

def get_hash(a, b):
    if a >= b:
        return 10000*a + b
    else:
        return 10000*b + a
v = []
N = int(input())
for i in range(N):
    nums = list(map(int, input().split()))
    pred = get_hash(i+1, nums[0])
    v.append(pred)
    for j in range(len(nums)-1):
        now = get_hash(i+1, nums[j+1])
        outs[pred].append(now)
        ins[now] += 1
        pred = now

v = set(v)
q = deque(v1 for v1 in v if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
if len(res) < (N*(N-1)) // 2:
    print(-1)
else:
    ans = 0
    before = []
    for h in res:
        a, b = get_ab(h)
        if (a in before) or (b in before):
            before = [a, b]
            ans += 1
        else:
            before.append(a)
            before.append(b)
    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
# a = [list(map(int, input().split())) ]
ans = 0
flag = True
while True:
    tmp = 0
    for j in range(n):
        if not a[j]:
            tmp += 1
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
    if tmp == n:
        print(ans)
        break
    for j in range(n):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
    if flag:
        print(-1)
        break
    else:
        ans += 1

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
    for _ in range(nn):
        pop_list = []
        pap = pop_list.append
        for i in range(n):
            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 sys

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

A.insert(0,[])

day = 0
pop_set = set()
#print(A)

while A:
  day += 1
  pop_set.clear()
  for i in range (1,N):
    if A[i]:
      vs = A[i][0]
      if A[vs][0] == i:
        pop_set.add(i)
        pop_set.add(vs)
  if pop_set == set():
    print(-1)
    sys.exit()
  #print(pop_set)
  for j in range(len(pop_set)):
    A[list(pop_set)[j]].pop(0)
  empty_judge = True
  for k in range(N):
    if A[k]:
      empty_judge = False
  if empty_judge:
    print(day)
    sys.exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=1
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if data[i]:
			aite=data[i][0]
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:continue
				if taisenzumi[aite-1]:continue				
				
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import count
N = int(input())
Ass = [deque(map(int, input().split())) for _ in range(N)]


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

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

    A = [tuple(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
    a = (N * (N - 1))//2
    d = 2 * N + 2
    c = N - 1
    while tmp < d:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= c or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == a:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()