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:
from collections import deque
import time
st = time.time()
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])

ans = 0
allpc = 0
tifl = False
while (True):
  if time.time() - st > 1.9:
    tifl = True
    break
  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 tifl or allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

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):
		# print("i:",i)
		## p1 = i
		pass1 = b[i][0]       
		# print("pass1:",pass1)
		if pass1 >= n-1: continue
		p2 = a[i][pass1] - 1  
		# print("p2:",p2)
		pass2 = b[p2][0]      
		# print("pass2:",pass2)
		if pass2 >= n-1: continue
		p3 = a[p2][pass2] - 1 
		# print("p3:",p3)
		
		if p3 == i:
			b[i][1] = max(b[i][1], b[a[i][b[i][0]] - 1][1]) + 1
			b[a[i][b[i][0]] - 1][1] = b[i][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 = tuple([
  tuple(map(lambda x: int(x)-1, input().split()))
  for _ in range(n)
])

from queue import PriorityQueue
pq = PriorityQueue()
pq.put((1, a, []))
known_state = {a}
while not pq.empty():
  p, a, u = pq.get()
  if sum([len(ai) for ai in a]) == 0:
    print(p)
    break
  flag = False
  for i, ai in enumerate(a):
    if not (i not in u and ai and a[ai[0]] and ai[0] not in u):
      continue
    if i == a[ai[0]][0]:
      pq.put((
        p, tuple([
          aj[1:] if j == i or j == ai[0] else aj
          for j, aj in enumerate(a)
        ]), u + [i, ai[0]]
      ))
      flag = True
  if not flag:
    if a in known_state:
      print(-1)
      break
    known_state.update(a)
    pq.put((p+1, a, []))

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = [collections.deque(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    players = set(range(n))

    while players:
        visited = set()
        removals = set()
        for i in players:
            if i in visited:
                continue
            
            x = a[i][0] # iの次候補
            if x in visited:
                continue

            y = a[x][0] # xの次候補
            if i == y:
                a[i].popleft()
                a[x].popleft()
                visited.add(i)
                visited.add(x)
                if not a[i]:
                    removals.add(i)
                if not a[x]:
                    removals.add(x)

        if visited:
            players -= removals
            day += 1
        else:
            return -1

    return day



print(f())

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A):
    days = 0
    n_games = N * (N-1) / 2
    game_index = [0] * (N+1)
    while n_games > 0:
        n_games_today = 0
        has_game_today = [False] * (N+1)
        for i in range(1, N+1):
            if has_game_today[i]:
                continue
            j = A[i][game_index[i]]
            if j != -1 and A[j][game_index[j]] == i:
                has_game_today[i] = True
                has_game_today[j] = True
                n_games_today += 1
        for i in range(1, N+1):
            if has_game_today[i]:
                game_index[i] += 1
        if n_games_today > 0:
            days += 1
            n_games -= n_games_today
        else:
            return -1
    return days


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        a += [-1, ]
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a)
count = 0
keys = [int(i) for i in dic.keys()]
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  pk = []
  for k in keys:
    if dic[k]==deque([]):
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==deque([]):
      print(-1)
      break
    pk += [k,p2]
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
  keys = pk
      
  if keys==[]:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            else:
                battle_dict.pop(i)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            else:
                battle_dict.pop(j)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

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
    for _ in range(10**9):
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]-1
            if  A[enemy][IDX[enemy]] == player+1:
                next_idx = i+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = i
        if flag:
            return -1
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

Submission status: Time Limit Exceeded

Solution code:
import 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()
    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 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:
from collections import deque

import sys
input = sys.stdin.readline


n = int(input())
a_list = {i:None for i in range(n)}
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(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 num >= n * (n - 1) // 2:
                            print(day)
                            exit()
    if (len(visit) == 0):
        print(-1)
        exit()
    if num >= n * (n - 1) // 2:
        print(day)
        exit()

Submission status: Time Limit Exceeded

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

ans = 0
allpc = 0
tifl = False
while (True):
  if time.time() - st > 1.95:
    tifl = True
    break
  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 tifl or allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque


def solve(N, A):
    day = 0
    total = (N * (N-1)) // 2
    players = set(range(N))
    while True:
        day += 1
        update = False
        today = set()
        loop_in_day = True
        ps = players.copy()
        while loop_in_day:
            loop_in_day = False
            ps1 = set()
            while ps:
                i = ps.pop()
                if i in today:
                    continue
                if not A[i]:
                    continue
                opp = A[i][0] - 1
                if opp in today:
                    continue
                if A[opp][0] - 1 == i:
                    A[i].popleft()
                    A[opp].popleft()
                    if not A[i]:
                        players.remove(i)
                    if not A[opp]:
                        players.remove(opp)
                    today.add(i)
                    today.add(opp)
                    total -= 1
                    update = True
                    loop_in_day = True
                    if total == 0:
                        return day
                else:
                    ps1.add(i)
            ps = ps1
        if not update:
            return -1


if __name__ == '__main__':
    N = int(input())
    A = []
    for _ in range(N):
        A.append(deque(map(int, input().split())))

    ans = solve(N, A)

    print(ans)

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

cnt = 0
match = N*(N-1)//2
d = 0

flag = True
while  cnt<match and flag:
    flag = False
    li = []
    d += 1
    for i in range(N):
        if i not in li and len(A[i])!=0:
            aite = A[i][-1]
            if  aite-1 not in li and i+1 == A[aite-1][-1]:
                flag = True
                cnt += 1
                A[aite-1].pop()
                A[i].pop()
                li.extend([aite-1,i])
            
if match == cnt:
    print(d)
else:
    print(-1)

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 = []
ans = 0
before = []
while q:
    v1 = q.popleft()
    res.append(v1)
    a, b = get_ab(v1)
    if (a in before) or (b in before):
        before = [a, b]
        ans += 1
    else:
        before.append(a)
        before.append(b)
    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:
    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

N = int(input())
As = [list(map(int,input().split())) for i in range(N)]
As = np.array(As)-1


current_waitings = As[:,0]
game_counter = np.zeros(N).astype('int')

day = 0
completed_players = []
day_player = []
for x in range(N*(N-1)//2):
    day_player = []
    for i,e1 in enumerate(current_waitings):
        if i in completed_players:
            continue
        if current_waitings[e1] == i and e1 not in day_player and i not in day_player:
            day_player.append(i)
            day_player.append(e1)
            if game_counter[i] == N-2:
                completed_players.append(i)
            if game_counter[i] <= N-3:
                game_counter[i] += 1
            if game_counter[e1] == N-2:
                completed_players.append(e1)
            if game_counter[e1] <= N-3:
                game_counter[e1] += 1
            current_waitings[i] = As[i][game_counter[i]]
            current_waitings[e1] = As[e1][game_counter[e1]]
        if len(completed_players) == N:
            print(day+1)
            sys.exit()
    day += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    A = [list(map(int,input().split())) for _ in range(N)]
    next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    check = [0 for _ in range(N)]
    while True:
        end = True
        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:
import sys
input=sys.stdin.readline
import collections

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

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

progress_list = [0] * N
next_list = [a[0] - 1 for a in A]

done_match = 0
day_limit = N * (N - 1) // 2 + 1
for i in range(day_limit):
    exhausted = [0] * N
    roop = True

    for man_idx in range(N):
        opponent_idx = next_list[man_idx]
        if (opponent_idx <= -1) or exhausted[opponent_idx] or exhausted[man_idx]:
            continue

        opponents_opponent = next_list[opponent_idx]
        if man_idx == opponents_opponent:
            # print('day', i + 1, ',', man_idx + 1, opponent_idx + 1)
            exhausted[man_idx] += 1
            progress_list[man_idx] += 1
            next_list[man_idx] = A[man_idx][progress_list[man_idx]] - 1

            exhausted[opponent_idx] += 1
            progress_list[opponent_idx] += 1
            next_list[opponent_idx] = A[opponent_idx][progress_list[opponent_idx]] - 1

            done_match += 1
            roop = False

    if roop:
        print(-1)
        exit()

    if done_match == N * (N - 1) // 2:
        print(i + 1)
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import copy

n = int(input())
a = []
for i in range(n):
    ai = list(map(int, input().split()))
    a.append(ai)

ind = [0 for i in range(n)]
ind_copy = copy.copy(ind)

# a = np.array(a)
# a = a - 1

ans = 0
while True:
    kanou = 0
    ans += 1
    senshu = set([i for i in range(n)])
    while senshu != set([]):
        i = senshu.pop()
        if ind[i] <= n-2:
            player = a[i][ind[i]]
        else:
            continue
        if ind[player-1] <= n-2:
            player_vs = a[player-1][ind[player-1]]
        else:
            continue
        if i == player_vs-1:
            senshu.remove(player-1)
            kanou = 1
            ind_copy[i] +=  1
            ind_copy[player-1] += 1
    if kanou == 0:
        hantei = 0
        for i in range(n):
            if ind[i] < n-2:
                hantei = 1
        if hantei == 1:
            ans = -1
        break
    ind = copy.copy(ind_copy)

if ans != -1:
    print(ans - 1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = [list(map(int, input().split())) for _ in range(N)]

        already_p = set()
        days = 0
        done = set()
        while True:
            for i, a in enumerate(A):
                if len(a) == 0:
                    done.add(i + 1)
                    continue
                if i + 1 not in already_p and a[0] not in already_p and A[a[0] - 1][0] == i + 1:
                    already_p.add(i + 1)
                    already_p.add(a[0])
                    A[a[0] - 1] = A[a[0] - 1][1:]
                    A[i] = a[1:]

            if len(done) == N:
                break

            if len(already_p) == 0:
                print(-1)
                exit()

            already_p = set()
            days += 1

        print(days)


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

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)
day = 0
while sum([len(row) for row in A]) > 0:
    pre = deepcopy(current)
    day += 1
    for i in range(N):
        if current[i + 1] == 0:
            if len(A[i]) > 0:
                current[i + 1] = A[i].popleft()
    for n in range(1, N + 1):
        pair = current[n]
        if pair > n and current[pair] == n:
            current.pop(n)
            current.pop(pair)

    if current == pre:
        print(-1)
        break
else:
    print(day)

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**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 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 sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque

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

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


def bfs():
    q = deque([])
    for root, rt in enumerate(isroot):
        if rt:
            q.append(root)
            match[root] = 1
    # print(match)
    while(q):
        item = q.popleft()
        inq[item] = False
        # print(q, item, child[item])
        for ch in child[item]:
            # print(ch)
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                if not inq[ch]:
                    q.append(ch)
                    inq[ch] = True

    return




for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        if i > j:
            ii, j = j, i
        else:
            ii = i

        if i > k:
            iii, k = k, i
        else:
            iii = i
        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()

bfs()
# print("gg")
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:
n = int(input())
a = [0] * (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 and i not in update:
            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)