Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

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

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

    else:
        N = _I()
        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.get(opponent_idx)[current_position_list.get(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())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
Ai = [0] * N
ans = 0
cnt_comp = 0
comp_set = set()
while True:
    cnt = 0
    visited = set()
    for i in range(N):
        if Ai[i] == N-1:
            comp_set.add(i)
            continue
        elif i in visited:
            continue
        oi = A[i][Ai[i]]
        if A[oi][Ai[oi]] == i and not oi in visited:
            Ai[i] += 1
            Ai[oi] += 1
            cnt += 1
            visited.add(i)
            visited.add(oi)
    if len(comp_set) == N:
        break
    elif cnt == 0:
        ans = -1
        break
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

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

for k in range(600000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    #print(index)

print(ans)

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():
                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:
                    skip.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(sys.stdin.readline().rstrip())
AList=[]
doneList=[False]*N
for i in range(N):
  AListTmp=list(map(int,sys.stdin.readline().split()))
  AList.append(AListTmp[::-1])

gameDays=0
maxGame=(N*(N-1))//2
gameCount=0
while(True):
  gameDays+=1
  doneList=[False]*N
  minimumDone=False
  for i in range(N):
    if doneList[i]==False and len(AList[i]) > 0:
      player1=i
      player2=AList[i][-1]-1
      if len(AList[player2]) == 0:
        print(-1)
        exit()
      if doneList[player2] == False and AList[player2][-1]-1 == player1:
        doneList[player1]=True
        doneList[player2]=True
        AList[player1].pop()
        AList[player2].pop()
        gameCount +=1
        minimumDone=True
        #print("{} day, {} {}".format(gameDays,player1,player2))
  if minimumDone==False:
    print(-1)
    exit()
  if gameCount >= maxGame:
    break
    
print(gameDays)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ann = [[0 for x in range(n-1)]]+[[int(x) for x in input().split()]for i in range(n)]
# print(ann)

indexes = [0 for x in range(n+1)]
#

days = 0
match_count = 0
fight_persons = set([])
while(match_count < (n*(n-1))//2):
    fight_persons = set([])
    # print(f"{days} day")
    # print(indexes)
    for self_i,an in enumerate(ann[1:]):
        self_i += 1
        # print(f"self_i = {self_i}")
        if self_i in fight_persons or len(an) <= indexes[self_i]:
            continue
        person_i = an[indexes[self_i]]
        # print(f"person_i = {person_i}")
        if person_i in fight_persons or len(ann[person_i]) <= indexes[person_i]:
            continue
        if ann[person_i][indexes[person_i]] == self_i:
            # print("fight!!!")
            # print(person_i,self_i)
            match_count += 1
            indexes[self_i] += 1
            indexes[person_i] += 1
            fight_persons.add(self_i)
            fight_persons.add(person_i)
    # print(fight_persons)
    if len(fight_persons) > 0:
        days += 1
    else:
        break


# print("+++++++++++++++")
if match_count < (n*(n-1))//2:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

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

flag2 = 0
flag3 = 0
n = 0
while(1):
    n = n + 1
    tmp_list = []
    flag = 0
    for i in l:
        if (i != []):
            flag = 1
    if flag == 1:
        if (flag2 == 1):
            if (flag3 == 1):
                break
            flag3 = 1
            continue
        flag2 = 1
        for i in range(N):
            if (i+1 in tmp_list):
                continue
            if l[i] == []:
                continue
            t = l[i][0]
            if not((i+1 in tmp_list) or (t in tmp_list)):
                if (l[t-1][0]==i+1):
                    tmp_list.append(i+1)
                    tmp_list.append(t)
                    l[i]=l[i][1:]
                    l[t-1]=l[t-1][1:]
                    flag2 = 0
                    flag3 = 1
    else :
        flag3 = 0
        break
if flag3 == 1:
    print(-1)
else:
    print(n-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    ans = 0
    count = 0
    MAX_COUNT = n * (n-1)
    iteration_times = 0
    flag = 0

    while iteration_times <= MAX_COUNT:
        iteration_times += 1

        if count == MAX_COUNT:
            flag = 1
            break
        
        numset = set()
        add = numset.add
        flag = 100
        for i in range(n):
            if len(L[i]) != 0 and i not in numset:
                a = L[i][0]
                b = L[a][0]
                if i == b:
                    add(i)
                    add(b)
                    flag = 0
        
        if flag == 100:
            break
        for elm in numset:
            L[elm].popleft()
            count += 1

        ans += 1

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [deque([int(s) for s in input().split()]) for i in range(N)]
count = 0
ismatch = False
while True:
  ismatch_list = [False for i in range(N)]
  if sum([len(a) for a in A]) == 0:
    break
  for i in range(N):
    if A[i] == deque([]) or ismatch_list[i] == True or ismatch_list[A[i][0]-1] == True:
      pass
    elif A[A[i][0]-1][0] == i+1:
      ismatch = True
      ismatch_list[A[i][0]-1] = True
      ismatch_list[i] = True
      A[A[i][0]-1].popleft()
      A[i].popleft()
  if ismatch:
    count += 1
    ismatch = False
  else:
    count = -1
    break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())

n2 = []

for i1 in range(n1):
    n2.append([int(i) for i in input().split()])

n3 = [0] * n1
r1 = 0

for i2 in range(500000):
    r1 += 1
    d1 = {}
    for i3 in range(n1 - 1):
        if n3[i3] >= n1 - 1:
            continue
        t2 = n2[i3][n3[i3]] - 1
        if n2[t2][n3[t2]] == (i3 + 1) :
            if i3 < t2:
                if d1.get(i3, 0) == 0:
                    if d1.get(t2, 0) == 0:
                        n3[i3] += 1
                        n3[t2] += 1
                        d1[i3] = 1
                        d1[t2] = 1

    if min(n3) >= (n1 - 1):
        break
    if len(d1) == 0:
        r1 = -1
        break

print(r1)

Submission status: Time Limit Exceeded

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

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

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

res = 0
cnt = 0
pcnt = [N-1]*N
m = N*(N-1)//2

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
input = sys.stdin.readline
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append([i+1,N[j]])
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] != 0:
      None
    else:
      B[i] = 1
      if dp[i] == n-1:
        None
      else:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          break
        else:
          if B[miru] != 1:
            sie = dp[miru]
            if L[miru][sie][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              act += 1
            else:
              None
          else:
              None
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque

  N = int(input())
  table = [list(map(int, input().split())) for i in range(N)]
#  table = []
#  for i in range(N):
#    H = deque()
#    A = input().split()
#    for a in A:
#      H.append(int(a))
#    table.append(H)      
  count = 0
#  cur = [0]*N
  for k in range(10**6):
    flag = 0
    game = [0]*N
    count += 1
    for i in range(N):
      if game[i] == 0 and len(table[i]) != 0:
        x = table[i][0]-1
        if game[x] == 0 and table[x][0] == i+1:
#          print(count,i,x)
          table[i].pop(0)
          table[x].pop(0)
#          cur[i] += 1
#          cur[x] += 1
          game[i] = 1
          game[x] = 1
          flag = 1
#    if any() == 0:
#      print(count)
#      exit()
    if flag == 0:
#      print(-1)
      break
#  print(table)
#  print(any(table))
  if any(table):
    print(-1)
  else:
    print(count-1)  

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.9:
            if N == 1000:
                print((N*(N-1))//2)
                break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)


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

visited = [[-1] *(len(a[0])) for i in range(n)]
memo = [[0] * (n) for i in range(n)]
for i in range(n):
    for j in range(len(a[0])):
        memo[i][a[i][j]-1] = j
        
def solve(i, j, rec_times):
    if rec_times >= 10000:
        print(-1)
        exit()
    i_me = i
    j_me = j
    i_you = a[i_me][j_me] - 1
    j_you = memo[i_you][i_me]
    if j_me == 0 and j_you == 0:
        visited[i_me][j_me] = 1
        visited[i_you][j_you] = 1
        return 1
    
    if visited[i_me][j_me] > 0 and not visited[i_you][j_you] > 0:
        return max(visited[i_me][j_me], visited[i_you][j_you])
 
    if j_you == 0:
        day = solve(i_me, j_me - 1, rec_times + 1) + 1
    elif j_me == 0:
        day = solve(i_you, j_you - 1, rec_times + 1) + 1    
    else:
        day = max(solve(i_me, j_me - 1, rec_times + 1), solve(i_you, j_you - 1, rec_times + 1)) + 1
    visited[i_me][j_me] = day
    visited[i_you][j_you] = day
    return day
    
for i in range(n):
    solve(i, len(a[0]) - 1, 0)
ans = 0
for i in range(n):
    ans = max(ans,visited[i][-1])
print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    a=list(map(int,input().split()))
    L.append(a)
#print(L)
Z=[0 for i in range(N+1)]
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):
        if Z[j]==N-1 or j in D:
            continue
        elif L[L[j][Z[j]]][Z[L[j][Z[j]]]]==j and L[j][Z[j]] not in D:
            D[j]=1
            D[L[j][Z[j]]]=1
            X=L[j][Z[j]]
            Z[j]+=1
            Z[X]+=1
            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:
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:
            continue
        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:
N = int(input())
match_l = []
for _ in range(N):
    match_l.append(list(map(int,input().split())))

day = 0
while(True):
    players = []
    fin_count = 0
    for i,match in enumerate(match_l):
        if(not match):
            fin_count += 1

        elif(i not in players):
            if(match_l[match[0]-1]):
                if(match_l[match[0]-1][0]-1==i):
                    players.append(i)
                    players.append(match[0]-1)

    if(fin_count == N):
        print(day)
        exit(0)
    if(not players):
        print(-1)
        exit(0)

    for player in players:
        match_l[player].pop(0)

    day += 1

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)
    
    L = [N-1 for _ in range(N)]
    games = N*(N-1)//2
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if L[i] == 0 or gamed[i] != 0:
                continue
            j = Q[i][0] - 1
            if L[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
                    L[i] -= 1
                    L[j] -= 1
                    gamed[i] = 1
                    gamed[j] = 1
                    games -= 1
                    continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(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)
                update.append(p)
    for j in update:
        todo[j] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    am = []

    from collections import deque

    for i in range(n):
        am.append(deque(list(map(lambda x: int(x) - 1, input().split()))))

    cnt = n * (n - 1) // 2

    day = 0
    while cnt > 0:
        day += 1
        match = 0
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j < i:
                continue
            if j not in done and am[j][0] == i:
                am[i].popleft()
                am[j].popleft()
                done[i] = 1
                done[j] = 1
                match += 1

        if match == 0:
            print(-1)
            return
        else:
            cnt -= match

    print(day)
    
resolve()

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 - 1):
    #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:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        #print(i,match,indexes,cnt)
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: #全試合done
                continue
            rival = A[k][index]
            if (k,rival) in match: #前回の希望相手との試合がまだ
                continue
            """else:
                indexes[k] += 1"""
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))
        #print(today_players)


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
n = N

data= [ [int(elm) - 1 for elm in input().split(" ")] for i in range(N)]
#print(data)

nexts = [0 for _ in range(n)]
goal = [N-1 for _ in range(n)]

day = 1
while True:
    done = False
    nows = []
    for jibun_i in range(n):
        next_i = nexts[jibun_i]
        if next_i == n-1:
            continue

        #print(jibun_i, next_i)
        aite_i = data[jibun_i][next_i]

        if data[aite_i][nexts[aite_i]] == jibun_i and jibun_i not in nows and aite_i not in nows:
            done = True
            nexts[jibun_i] += 1
            nexts[aite_i] += 1
            nows += [jibun_i, aite_i]

    if goal == nexts:
        out = day
        break
    if not done:
        out = -1
        break
    
    day += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [list(int(_) for _ in input().split()) for i in range(n)]
x = [0]*n
s = set(list(range(n)))
chk = -1

for i in range(n*(n+1)+1):
    if i % 1000 == 0:
        if sum(x) == chk:
            print(-1)
            break
        else:
            chk = sum(x)
    
    if len(s) == 0:
        print(i)
        break
    z = [l[ii][x[ii]] for ii in range(n)]
    sdel = set()
    for ii in s:
        if z[z[ii]-1] == ii + 1:
            if x[ii] <= n - 3:
                x[ii] = x[ii]+1
            else:
                sdel.add(ii)
    [s.remove(ii) for ii in sdel]
    if i == n*(n+1):
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = [deque(list(map(int, input().split()))) for _ in range(n)]

now = []
for i in range(n):
    now.append(a[i].popleft()-1)
# print(a)
# print(now)

ans = 0
battle = 0
max_battle = n*(n-1)//2
while battle < max_battle:
    checked = [False]*n
    nogame = True
    for i in range(n):
        x = i
        y = now[i]
        if checked[i] or checked[y] or now[i]==-1:
            continue
        checked[i] = True
        if now[y]==i:
            checked[y] = True
            if a[x]:
                now[x] = a[x].popleft()-1
            else:
                now[x] = -1
            if a[y]:
                now[y] = a[y].popleft()-1
            else:
                now[y] = -1
            battle += 1
            nogame = False
            # print(i, now)

    if nogame:
        print(-1)
        exit()
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,random

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

def main():
  n=I()

  l=[]
  for _ in range(n):
    _l=LI()
    _l.reverse()
    l.append(_l)

  c=n*(n-1)
  ans=1
  nagasa=[n-1]*n

  while True:
    m=[0]*n
    _c=c

    x=list(range(n))
    random.shuffle(x)
    for i in x:
      if c<=0:
        return ans

      if m[i]!=0:
        continue

      if nagasa[i]!=0:
        a=l[i][-1]-1

        # if a<i:
        #   continue

        if m[a]!=0:
          continue

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

    if _c==c:
      return -1

    ans+=1

# main()
print(main())