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:
#

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

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

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

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

            if agrid[target][agrid_pointer[target]] == i:
                # can match
                agrid_pointer[i] += 1
                agrid_pointer[target] += 1

                match.add(i)
                match.add(target)
            else:  # 次対戦できないからのその対戦相手とのマッチを試す
                target_target = agrid[target][agrid_pointer[target]]
                if agrid_pointer[target_target] == n - 1 or target_target in match:  # もう全部対戦済み or この日対戦済み
                    continue
                if agrid[target_target][agrid_pointer[target_target]] == target:
                    # can match
                    agrid_pointer[target_target] += 1
                    agrid_pointer[target] += 1

                    match.add(target_target)
                    match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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] = [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()
    while True:
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

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

            if i in all_done_players:
                # この選手はすべての試合を終了している
                continue

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

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

            # iの試合相手の次の相手が選手iなら成立する
            if A_list[opponent_idx][current_position_list[opponent_idx]] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                done_player_list.add(opponent_idx)
                done_player_list.add(i)
                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:
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = [int(j) - 1 for j in input().split()]
    A[i] += reversed(a)

ans = 0
while(True):
    flag = False
    game_flag = [False] * N
    for i in range(N):
        if game_flag[i] == False and A[i] != []:
            j = A[i][-1]
            if game_flag[j] == False and A[j] != [] and A[j][-1] == i:
                flag = True
                game_flag[i] = True
                game_flag[j] = True
                A[i].pop()
                A[j].pop()
    ans += 1
    if A == [[] for i in range(N)]:
        break
    elif flag == False:
        ans = -1
        break

print(ans)

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
    lst = []
    flag =[True] * (N+1)
    for i in range(1,N+1):
        if flag_max[i]:continue
        if not(flag[i]):continue
        tmp = A[i][idx[i]]
        if not(flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            lst.append(i)
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                cnt += 1
                flag_max[tmp] = True
            if idx[i] == N-1:
                cnt += 1
                flag_max[i] = True
            flag[i] = False
            flag[tmp] = False
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())

a = [[] for _ in range(n)]
status = [[0, 0] for _ in range(n)]

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

a.append([-1])
status.append([0])

changed = 0
end = 0

while True:
    for i in range(n):
        enemy = a[i][status[i][0]] - 1
        if a[enemy][status[enemy][0]] == i + 1:
            day = max(status[i][1], status[enemy][1])
            status[i][1] = day + 1
            status[enemy][1]= day + 1

            if status[i][0] == n-2:
                a[i][n-2] = n + 1
                end += 1
            else:
                status[i][0] += 1

            if status[enemy][0] == n-2:
                a[enemy][n-2] = n + 1
                end += 1
            else:
                status[enemy][0] += 1

            changed = 1

    if end == n:
        break
    if changed == 0:
        print(-1)
        exit()
    changed=0

ans = 0
for i in range(n):
    ans = max(status[i][1], ans)

print(ans)

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 = [False]*N
    for i in range(N):
        if played[i] or game[i] >= N-1: 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:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3): 
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      amat[i].pop()
      amat[ai_next].pop()
      matched_flag[i]=True
      matched_flag[ai_next]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    maxlist=-1
    for i in range(1,N+1):
      maxlist=max(maxlist,len(amat[i]))
    if maxlist==0:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
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()
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already or i in already:
                continue
            if i == next_pos[now] - 1:
                if end:
                    end = False
                if A[i]:
                    next_pos[i] = A[i].pop(0)
                else:
                    next_pos[i] = 0
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = 0
                already.add(i)
                already.add(now)
        ans += 1
        if end:
            ans = -1
            break
        if next_pos == check:
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N=int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for _ in [0]*N]

Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
Eb = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        Eb[k1].append(k0)
Ef = {k:set(v) for k,v in Ef.items()}
Eb = {k:set(v) for k,v in Eb.items()}

q = [k for k in Eb if Eb[k] == set()]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            Eb[k2].remove(k)
            rmv += 1
            if not Eb[k2] : qq.append(k2)
        Ef[k] = set()
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

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 & A[j][game_index[j]] == i:
                has_game_today[i] = True
                has_game_today[j] = True
        n_games_today = sum(has_game_today) // 2
        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:
# ABC139
def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = A[x : x + N - 1]
    C = {i: 0 for i in range(1, N + 1)}
    ans, flg, matched = 0, 0, set()
    while C:
        for i in list(C.keys()):
            if i in C and i not in matched:
                x = B[i][C[i]]
                if x in B and x not in matched and B[x][C[x]] == i:
                    C[i] += 1
                    C[x] += 1
                    matched |= {i, x}
                    flg = 1
                    if C[i] == N - 1:
                        del C[i]
                    if C[x] == N - 1:
                        del C[x]
        if flg:
            ans += 1
            flg, matched = 0, set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N=int(input())
L=[[]]

for i in range(N):
    a=deque(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        #print(L[j],j)
        if len(L[j])==0 or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            del L[j][0]
            del L[X][0]
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

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
    while True:
        day += 1
        update = False
        today = set()
        loop_in_day = True
        while loop_in_day:
            loop_in_day = False
            for i in range(N):
                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()
                    today.add(i)
                    today.add(opp)
                    total -= 1
                    update = True
                    loop_in_day = True
                    if total == 0:
                        return day
        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:
def scheduler(N, A):
    days = 0
    while True:
        games = []
        no_player = True
        for i in range(N):
            if len(A[i]):
                no_player = False
                oppo = A[i][0] -1
                if A[oppo][0] - 1 == i:
                    games.append(i)
        if no_player:
            break
        days += 1
        if len(games) == 0:
            return(-1)
        for game in games:
            del A[game][0]
    return(days)

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

print(scheduler(N, A))

Submission status: Time Limit Exceeded

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

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
while(1):
    flag = 0
    match_array = [0] * N
    for i in range(N):
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
print(ans_date)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int, input().split())) for _ in range(N)]
A.insert(0,[0]*(N-1))
day=0
fin=[0]*(N+1)
no_match=True
impossible=False
while sum(fin) < N:
  no_match=True
  fighter=[False]*(N+1)
  for i in range(1,N+1):
    if fin[i]==1:
      continue
    f=A[i][0]
    if fighter[i] or fighter[f]:
      continue
    if A[f][0]==i:
      no_match=False
      fighter[i]=True
      fighter[f]=True
      A[i]=A[i][1:]
      A[f]=A[f][1:]
      if len(A[i])==0:
        fin[i]=1
      if len(A[f])==0:
        fin[f]=1
  if no_match:
    impossible=True
    break
  day+=1
if impossible:
  print(-1)
else:
  print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
now=[[0,0] for i in range(n)]
day=0
sumsiai=0
end=n*(n-1)//2
while 1:
    day+=1
    siaisuu=sumsiai
    for i in range(n):
        if now[i][0]==n-1 or now[i][1] == day:
            continue
        nex=a[i][now[i][0]]
        if i+1==a[nex-1][now[nex-1][0]] and now[nex-1][1] != day:
            siaisuu+=1
            now[i][0]+=1
            now[i][1],now[nex-1][1]=day,day
            now[nex-1][0]+=1
    if siaisuu-sumsiai==0:
        print(-1)
        quit()
    if siaisuu==end:
        print(day)
        quit()
    sumsiai=siaisuu

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    N=int(input())
    A=[[]]
    for _ in range(N):
        A.append(deque(map(int, input().split())))

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N
#F = [A[i][0] - 1 for i in range(N)]

def get_num(i):
    p = P[i]
    if p >= N - 1:
        return -1
    return A[i][p] - 1


def update(mem):
    for i in mem:
        P[i] += 1


def f():
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if P.count(N - 1) == N:
            return t

        for i in range(N):
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1

        update(mem)
        mem = set()

    return -2

print(f())

Submission status: Time Limit Exceeded

Solution code:

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
    lst = []
    flag =[True] * (N+1)
    for i in range(1,N+1):
        if flag_max[i]:continue
        if not(flag[i]):continue
        tmp = A[i][idx[i]]
        if not(flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            lst.append(i)
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                cnt += 1
                flag_max[tmp] = True
            if idx[i] == N-1:
                cnt += 1
                flag_max[i] = True
            flag[i] = False
            flag[tmp] = False
            error = False
    if error:
        import sys
        print(-1)
        sys.exit()
    
    day += 1
            
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
d={}
for i in range(N):
	d[i+1] = list(map(int,input().split()))
idx=[0]*(N+1)


cnt=0
while True:
	
	f=True
	p=[]
	num_e=0
	for i in d:
		if idx[i]>N-2:
			num_e+=1
		else:
		 	j=d[i][idx[i]]
		 	if d[j]!=[] and d[j][idx[j]]==i and (i not in p) and (j not in p): 
		 		idx[i]+=1
		 		idx[j]+=1
		 		p.append(i)
		 		p.append(j)
		 		f=False
	if num_e==N:
		print(cnt)
		break
		
	if f:
		print(-1)
		break
	cnt+=1

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append([int(a)-1 for a in input().split()])

    cur = [0 for _ in range(N)]
    count = 0
    matches = 0
    totmatch = N * (N-1)//2
    while matches != totmatch:
        count += 1
        used = set()
        for i in range(N):
            if i not in used and cur[i] != -1:
                j = A[i][cur[i]]
                if j not in used and cur[j] != -1 and A[j][cur[j]] == i:
                    used.add(i)
                    used.add(j)
                    matches += 1
        if len(used) == 0:
            return -1

        for i in used:
            cur[i] += 1
            if cur[i] == len(A[i]):
                cur[i] = -1
    return count


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

Submission status: Time Limit Exceeded

Solution code:
import heapq

n=int(input())
alist=[]
nowlist=[]
klist=[]
incre=0
error=0
day=0
 
for i in range(n):
    alist.append(list(map(int, input().split())))
 
for i in range(n):
    nowlist.append(0)
 
while error==0 and incre<n*(n-1):
    koho=[]
    for i in range(n):
        if nowlist[i]<n-1:
            if i+1>=alist[i][nowlist[i]]:
                small=[i+1, alist[i][nowlist[i]]]
            else:
                small=[alist[i][nowlist[i]], i+1]
            heapq.heappush(koho, small)
    koho=sorted(koho)
    swit=0
    for i in range(len(koho)-1):
        if koho[i]==koho[i+1]:
            nowlist[koho[i][0]-1]+=1
            nowlist[koho[i][1]-1]+=1
            incre+=2
            swit=1
    day+=1
    if swit==0:
        day=-1
        error=1
    #print(nowlist)
 
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())


from collections import deque

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

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

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

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

        # 一日経過
        cnt += 1

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

    print(cnt)


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    bbb = 0

    for i in range(n):
        if ls[i] != -1:
            mt[i] = a[i][ls[i]]

    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        bb = False
        update = []
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        f[i] = True
                        f[mt[i]-1] = True
                        bb = True
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            update.append(i)
                        else:
                            ls[i] = -1
                            bbb += 1

                        if ls[mt[i]-1] + 1 < n - 1:
                            ls[mt[i]-1] += 1
                            update.append(mt[i]-1)
                        else:
                            ls[mt[i]-1] = -1
                            bbb += 1
        for i in update:
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]

        if bbb == n:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    A = XLMIIS(N)
    days = 0
    idxs = [0] * N
    while True:
        #print(A)
        firstgame = True
        matched = False
        desired = [ A[i][idxs[i]] for i in range(N)]
        # desired = []
        # for i in range(N):
        #     idx = idxs[i]
        #     l = A[i]
        #     #print(N,idx)
        #     desired.append(l[idx])
        #print(desired)

        if desired.count(-1) == N:
            print(days)
            return

        for i in range(N):
            a = desired[i]
            if a < 0:
                continue
            b = desired[a-1]
            if b < 0:
                continue
            # matched
            if b == i+1:
                # A[a-1].pop(0)
                # if len(A[a-1]) == 0:
                #     A[a-1].append(-1)
                # A[i].pop(0)
                # if len(A[i]) == 0:
                #     A[i].append(-1)
                # desired[a-1] = -1
                idxs[i] += 1
                if idxs[i] == N-1:
                    idxs[i] = N-2
                    A[i][-1] = -1

                desired[a-1] = -1
                idxs[a-1] += 1
                if idxs[a-1] == N-1:
                    idxs[a-1] = N -2
                    A[a-1][-1] = -1
                
                if firstgame:
                    firstgame = False
                    matched = True
                    days += 1
        if matched == False:
            print(-1)
            return 
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque


def dfs(root, links):
    pending = set()
    ans = 0
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            ans = max(ans, d)
            q.append((v, 1))
            pending.add(v)
            d += 1
            for u in links[v]:
                if u in pending:
                    return False
                q.append((u, 0, d))
        else:
            pending.remove(node[0])
    return ans


n = int(input())
links = defaultdict(set)
may_root = set()
in_cnt = defaultdict(lambda: 0)
for i, line in enumerate(sys.stdin):
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    a, b = (i, j) if i < j else (j, i)
    prev = a * 1000 + b
    may_root.add(prev)

    for j in aaa[1:]:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * 1000 + b
        links[prev].add(key)
        in_cnt[key] += 1
        prev = key
may_root = {r for r in may_root if in_cnt[r] == 0}

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

ans = dfs(may_root, links)
if ans == False:
    print(-1)
    exit()

print(ans)