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:
n = int(input())
import collections
plan = {}
for i in range(n):
    plan[i+1] = collections.deque(list(map(int, input().split())))

remain = [player for player in range(1,n+1)]
cnt = 0
while remain != []:
    visit = [p for p in remain]
    flag = True
    while visit != []:
        p_check = visit.pop()
        if plan[p_check][0] in visit and plan[plan[p_check][0]][0] == p_check:
            visit.remove(plan[p_check][0])
            plan[plan[p_check][0]].popleft()
            plan[p_check].popleft()
            flag = False 
    if flag:
        cnt = -1
        break
    cnt += 1
    if cnt >= n-1:
        items = list(plan.items())
        for key, val in items:
            if len(val) == 0:
                remain.remove(key)
                del plan[key]
print(cnt)

Submission status: Time Limit Exceeded

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

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


for _ in range(total_match):
    day+=1
    today_match=[]

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

print(day)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[List[int]]"):
    flag = True
    counter = 0
    while flag:
        tmp = [a[0] for a in A]
        p_idx = []
        for i, t in enumerate(tmp):
            if i == tmp[t]:
                p_idx.append(i)
        if len(p_idx) == 0 or counter > N * 100:
            print(-1)
            return
        for p in p_idx:
            A[p].pop(0)
            A[p].append(-1)
        if all([a[0] == -1 for a in A]):
            flag = False
        counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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)) - 1 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:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if ans > N * (N - 1) // 2 + 1:
        print(-1)
        exit()
    # print(l, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
n=int(input())
v=n**2
A=[list(map(lambda x: int(x)-1,input().split())) for _ in range(n)]
Edges=set()
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.add((fr_i*n+fr_j,to_i*n+to_j))
outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in Edges:
    outs[v1].append(v2)
    ins[v2] += 1
q = deque((v1,1) for v1 in range(v) if ins[v1] == 0 and outs[v1])
res = []
while q:
    v1,d = q.popleft()
    res.append((v1,d))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,d+1))
print(res[-1][1] if len(res)==n*(n-1)//2 else -1)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = [[int(i) for i in input().split()] for _ in range(a)]
counter = 0
yesno = True
while len(b) != 0:
    found = False
    done = [False] * len(b)
    for i in range(len(b)):
        if len(b[i]) >= 1 and not done[i]:
            target = b[i][0]-1
            if not done[target] and len(b[target]) >= 1:
                if b[target][0] == i+1:
                    b[i].pop(0)
                    b[target].pop(0)
                    done[i] = True
                    done[target] = True
                    found = True
    if not found:
        break
    counter += 1
for a in b:
    if a != []:
        yesno = False
if not yesno:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

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

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

current = defaultdict(lambda: 0)
pre = {}
day = 0
while sum([len(row) for row in A]) > 0:

    day += 1
    for n in range(N, 0, -1):
        if current[n] == 0:
            if len(A[n - 1]) > 0:
                current[n] = A[n - 1].popleft()

        pair = current[n]
        if pair > n and current[pair] == n:
            current.pop(n)
            current.pop(pair)

    if current == pre and current != {}:
        print(-1)
        break

    pre = deepcopy(current)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
import collections

As = [collections.deque()]
for i in range(N):
    As.append(collections.deque(map(int, input().split())))

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))
# print(a)
b = [[0, 0] for _ in range(n)]
# print(b)
cnt = 0
cntmax = n*(n-1)
while cnt < cntmax:
	flag = True
	for i in range(n):
		pass1 = b[i][0]       
		if pass1 >= n-1: continue
		pass2 = b[a[i][pass1] - 1 ][0]      
		if pass2 >= n-1: continue
		
		if a[a[i][pass1] - 1][pass2] - 1 == i:
			b[a[i][b[i][0]] - 1][1] = b[i][1] = max(b[i][1], b[a[i][b[i][0]] - 1][1]) + 1
			b[a[i][b[i][0]] - 1][0] += 1
			b[i][0] += 1
			cnt += 2
			flag = False
			# print("done");print(a);print(b)
	if flag:
		print(-1)
		exit()
	# print(a)
	# print(b)
ans = 0
for i in range(n):
	ans = max(ans, b[i][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[]]
for i in range(N):
    lst = list(map(int,input().split()))
    lst.reverse()
    A.append(lst)
checklist = [0] * (N+1)
day = 0
total = 0
flg = True
#どうせTLE
while flg:
    flg = False
    for i in range(1,N+1):
        if A[i] and A[A[i][-1]]:
            enemy = A[i][-1]
            if A[enemy][-1] == i and checklist[enemy] == 0 and checklist[i] == 0:
                checklist[i] = 1
                checklist[enemy] = 1
                A[enemy].pop(-1)
                A[i].pop(-1)
                total += 1
                flg = True
                
    checklist = [0] * (N+1)
    day += 1

if total == (N*(N-1)//2):
    print(day-1)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def seek_candidates(current_A):
    can_set = []
    seeked_set = set()
    for n in range(N):
        if(n+1 not in seeked_set):
            if(current_A[n+1] != []):
                if(current_A[current_A[n+1][0]][0] == n + 1):
                    tmp = set([n+1, current_A[n+1][0]])
                    can_set.append(tmp)
                    seeked_set = seeked_set | tmp
    return can_set

def make_next_A(current_A, battles):
    for battle in battles.values():        
        for b in battle:
            current_A[b] = current_A[b][1:]

def make_battle_set(can_set):
    battle_set = collections.Counter()
    battle_players = set()
    index = 0
    for c in can_set:        
        if(c & battle_players == set()):
            battle_set[index] = c
            index += 1
            battle_players = battle_players | c
    return battle_set

import collections

currnet_A = collections.Counter()
N = int(input())
for n in range(N):
    currnet_A[n+1] = list(map(int, input().split()))

success_flag = False
loop_count = 0
remain_battles = int(N*(N-1)/2)

while(True):
    loop_count += 1
    can_set = seek_candidates(currnet_A)
    if(can_set == []):
        break
    battle_set = make_battle_set(can_set)
    make_next_A(currnet_A, battle_set)
    remain_battles -= len(battle_set)
    if(remain_battles <= 0):
        success_flag = True
        break
if(success_flag):
    print(loop_count)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

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

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

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

    """

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

        for i in range(N_1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if done_player_list.get(i):
                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 done_player_list.get(opponent_idx):
                # 試合相手がすでに今日試合してた場合
                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[i] = True
                #  done_player_list.add(opponent_idx)
                done_player_list[opponent_idx] = True
                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 = {}
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

orders = {i+1:list(map(int,input().split())) for i in range(n)}

day = 1
played = [False]*(n+1)
isplayed = False
finished = [False]*(n+1)
fcount = 0

while fcount < n:
  tmp = fcount
  for i in range(1,n+1):
    #print(i)
    if finished[i] or played[i]:
      continue
    if finished[orders[i][0]]:
      tmp = fcount; isplayed = False; break
    if played[orders[i][0]]:
      continue
    if i == orders[orders[i][0]][0]:
      #print("day:",day," i: ",i," opp: ",orders[i][0])
      played[i]=True; played[orders[i][0]]=True
      isplayed = True
      
      a = orders[i].pop(0)
      if len(orders[i]) == 0:
        finished[i] = True; fcount += 1
      orders[a].pop(0)
      if len(orders[a]) == 0:
        finished[a] = True; fcount += 1
  
  
  if tmp == fcount:
    if isplayed == True:
      isplayed = False
      played = [False]*(n+1)
      day += 1
    else:
      break


if fcount < n :
  print(-1)
else:
  print(day)

Submission status: Time Limit Exceeded

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

total = N*(N-1)//2
progress = [0]*N
battled = [False]*N
any_battle = False
day = 1
finished = 0
battle_count = 0
for _ in range(total):
    for man in range(N):
        if progress[man] >= N-1 or battled[man]:
            continue
        rival = A[man][progress[man]] - 1
        if battled[rival]:
            continue
        if A[rival][progress[rival]] - 1 == man:
            progress[man] += 1
            progress[rival] += 1
            battled[man], battled[rival] = True, True
            any_battle = True
            if progress[man] == N-2:
                finished += 1
            if progress[rival] == N-2:
                finished += 1
            battle_count += 1
            if battle_count == total:
                break
    battled = [False]*N
    day += 1
    if finished == N:
        print(day)
        break
    if not any_battle:
        print(-1)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

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

        you = game[me][0]
        if finish[you] == 1 or game[you] == deque([]):
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                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 = []
rem = N * (N-1) // 2
for _ in range(N):
    *temp, = map(int, input().split())
    A.append(temp)
day = 0
game = [0]*N
while rem:
    day += 1
    impossible = True
    played = {i: False for i in range(N) if game[i] < N-1}
    for i in played.keys():
        if played[i]: continue
        opposite = A[i][game[i]] - 1
        if not played[opposite] and i+1 == A[opposite][game[opposite]]:
            impossible = False
            played[i] = True; played[opposite] = True;
            rem -= 1
            game[i] += 1; game[opposite] += 1
    if impossible: print(-1); break
else:
    print(day)

Submission status: Time Limit Exceeded

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

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in range(N):
    #print(A, i)
    if A[i][0] > i:
      if (A[A[i][0] - 1][0] == i + 1) and (finish[i] == 0) and (finish[A[i][0]-1] == 0): #対戦可能な場合対戦。
        x = A[i][0]
        A[i].pop(0)
        A[x - 1].pop(0)
        finish[i] = 1
        finish[x-1] = 1
        if len(A[i]) == 0:
          A[i].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import functools
@functools.lru_cache(maxsize=None)

def main():
    n=int(input())
    d=defaultdict(deque)
    for i in range(n):
        d[i+1]=deque(map(int,input().split()))

    c=0
    immortalskip=set()
    while any(d.values()):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy() and i not in immortalskip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
alist = []
for i in range(n):
    alist.append(list(map(int, input().split())))
 
point = 0
kazu = 0
while True:
    y = []
    for i in range(n):
        if i not in y and len(alist[i]) > 0:
            for j in range(i, n):
                if i not in y and j not in y and len(alist[i]) > 0 and len(alist[j]) > 0:
                    if alist[i][0] - 1 == j and alist[j][0] - 1 == i:
                        alist[i].pop(0)
                        alist[j].pop(0)
                        y.append(i)
                        y.append(j)
                        point += 1
    if len(y) == 0:
        print(-1)
        sys.exit()
    kazu += 1
    if n*(n-1)/2 == point:
        print(kazu)
        sys.exit()

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())))
# print(a)
b = [[0, 0] for _ in range(n)]
# print(b)
cnt = 0
cntmax = n*(n-1)
while cnt < cntmax:
	flag = True
	for i in range(n):
		pass1 = b[i][0]       
		if pass1 >= n-1: continue
		pass2 = b[a[i][pass1] - 1 ][0]      
		if pass2 >= n-1: continue
		
		if a[a[i][pass1] - 1][pass2] - 1 == i:
			b[a[i][b[i][0]] - 1][1] = b[i][1] = max(b[i][1], b[a[i][b[i][0]] - 1][1]) + 1
			b[a[i][b[i][0]] - 1][0] += 1
			b[i][0] += 1
			cnt += 2
			flag = False
			# print("done");print(a);print(b)
	if flag:
		print(-1)
		exit()
	# print(a)
	# print(b)
ans = 0
for i in range(n):
	ans = max(ans, b[i][1])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)

deps = {}
for i in range(N):
    prevmatch = (i, i)
    for j in range(len(A[i]) - 1, -1, -1):
        if A[i][j] > i:
            match = (i, A[i][j])
        else:
            match = (A[i][j], i)
        deps.setdefault(prevmatch, []).append(match)
        prevmatch = match


days = {}
maxday = 0
queue = {}
for i in range(N):
    queue[(i, i)] = (0, set())
while len(queue) > 0:
    match, value = queue.popitem()
    day, hist = value
    if match in hist:
        print('-1')
        sys.exit()
    hist.add(match)
    if match in days and days[match] >= day:
        continue
    days[match] = day
    if maxday < day:
        maxday = day
    for depmatch in deps.get(match, []):
        if depmatch in queue and queue[depmatch][0] >= day + 1:
            continue
        queue[depmatch] = (day + 1, hist.copy())
print(maxday)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 10000:
        print(N*(N-1)//2)
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

team_dict = {}
for i in range(N):
    temp_str = input()
    temp_list = temp_str.split(" ")
    mapped_list = list(map(lambda x: int(x), temp_list))
    team_dict[i+1] = mapped_list

result = 0
empty_list_count = 0

while True:
    if empty_list_count == N:
        break
    delete_list = []
    for i in range(N):
        index = i + 1
        try:
            pear_index =  team_dict[index][0]
        except:
            continue
        if index == team_dict[pear_index][0]:
            delete_list.append(index)
    if len(delete_list) == 0:
        break
    result += 1
    for i in delete_list:
        team_dict[i].pop(0)
        if len(team_dict[i]) == 0:
            empty_list_count += 1

if empty_list_count == N:
    print(result)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

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

	
played_flg = 1
day = 0
played_game = 0
need_game = N * (N - 1) / 2

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from sys import stdin
import copy


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, stdin.readline().rstrip().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  Rev = set([i for i in range(N)])
  while len(Rev) > 0:
    dct = defaultdict(lambda:set([]))
    game = 0
    for i in copy.deepcopy(Rev):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game,Pn[i],Pn[j] = [game+1,Pn[i]+1,Pn[j]+1]
          if Pn[i] >= N-1:
            Rev.remove(i)
          if Pn[j] >= N-1:
            Rev.remove(j)
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
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:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    players = []
    for i in range(N):
        pl = deque(map(int, input().split()))
        for x in range(len(pl)):
            pl[x] = pl[x] - 1
        players.append(pl)

    max_match = int(N * (N-1) / 2)
    match_count = 0
    days = 0

    for i in range(max_match):
        played = deque()
        no_match = True

        for p in range(len(players)):
            main_p = p

            if main_p in played:
                continue

            if players[main_p]:
                opponent = players[main_p][0]

                if opponent in played or len(players[opponent]) == 0:
                    continue

                if main_p == players[opponent][0]:
                    no_match = False
                    played.append(players[main_p].popleft())
                    played.append(players[opponent].popleft())
                    match_count += 1

                    if match_count == max_match:
                        print(days + 1)
                        sys.exit()

        if no_match:
            print(-1)
            sys.exit()

        days += 1

    if days:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    main()