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 sys
input = sys.stdin.readline

n = int(input())

match = n * (n - 1) // 2
day = 0
waiting = []
finished = 0
for i in range(n):
    waiting.append(list(map(int, input().split())))

while match != 0:
    ml = [0] * n
    for i, wait_l in enumerate(waiting):
        if len(wait_l) == 0 or len(waiting[wait_l[0] - 1]) == 0:
            continue
        if ml[i] == 0 and ml[wait_l[0] - 1] == 0:
            if (i + 1) == waiting[wait_l[0] - 1][0]:
                ml[i] = 1
                ml[wait_l[0] - 1] = 1
                if len(waiting[i]) != 1:
                    waiting[i] = waiting[i][1:]
                else:
                    waiting[i] = []
                    finished += 1
                if len(waiting[wait_l[0] - 1]) != 1:
                    waiting[wait_l[0] - 1] = waiting[wait_l[0] - 1][1:]
                else:
                    waiting[wait_l[0] - 1] = []
                    finished += 1
                match -= 1
    if sum(ml) != 0:
        day += 1
        if finished == n:
            print(day)
            exit()
    else:
        print("-1")
        exit()

Submission status: Time Limit Exceeded

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

    days = 0
    changed = True
    played = set()
    while changed:
        played.clear()
        changed = False
        for i in range(N-1):
            if len(A[i]) == 0:
                continue
            a1 = A[i][0]
            if len(A[a1-1]) == 0:
                continue
            a2 = A[a1-1][0]
            if a1 in played or a2 in played:
                continue
            if a2-1 == i:
                A[a2-1].popleft()
                A[a1-1].popleft()
                played.add(a2)
                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:
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
        blocked = {}
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j in blocked:
                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
            else:
                blocked[i] = 1

            if match == cnt:
                break

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

    print(day)
    
resolve()

Submission status: Time Limit Exceeded

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

output = 0
memo = [0] * N
newmemo = [0] * N
owari = [0] * N
flag = 0
while flag < N:
    ng = 0
    for i in range(N):
        if (memo[i] == N-2) and (owari[i]==1):
            continue
        check = A[i][memo[i]]-1
        if i==A[check][memo[check]]-1:
            if memo[i] < N-2:
                newmemo[i]+=1
            elif (memo[i] == N-2) and (owari[i]==0):
                owari[i] = 1
                flag += 1
            elif (memo[i] == N-2) and (owari[i]==1):
                continue
        else:
            ng += 1
    if ng == N:
        output = -1
        break
    memo = newmemo[:]
    output += 1

print(output)

Submission status: Time Limit Exceeded

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

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)

empty = [[] for i in range(N)]
ans = 0
for _ in range(N * (N - 1) // 2):
    flag = False
    game_flag = [False] * N
    for i in range(N - 1,-1,-1):
        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 == empty:
        break
    elif flag == False:
        ans = -1
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a = []
for i in range(n):
    k = [int(x) for x in input().split()]
    j = []
    for i in range(1, len(k)+1):
        j.append(k[-i])
    a.append(j)
ans = 0
while a:
    s = 1
    todaylist = []
    for i in range(n):
        if i+1 in todaylist:
            continue
        if a[i]:
            if a[i][-1] in todaylist:
                continue
            b = a[i][-1]-1
            if a[b]:
                if a[b][-1] == i+1:
                    a[i].pop()
                    a[b].pop()
                    todaylist.append(i+1)
                    todaylist.append(b+1)
                    s = 0
    ans += 1
    if s:
        print(-1)
        sys.exit()
    if not any(a):
        break
print(ans)

Submission status: Time Limit Exceeded

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

import sys

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= [ int(x)-1 for x in sys.stdin.readline().split() ]
#
tot= (n*(n-1))//2
now= 0
c= 0
idx= [ 0 for _ in range(n) ]
flags= [ False for _ in range(n) ]
for _ in range(tot):
    nn= 0
    for i in range(n):
        if flags[i]: continue
        if idx[i]==n-1: continue
        j = a[i][idx[i]]
        aj = a[j]
        if aj[idx[j]]==i:
            nn+=1
            flags[i]= True
            flags[j]= True
    #
    if nn==0: break
    for i in range(n):
        if flags[i]:
            flags[i]= False
            idx[i]+=1
    #
    c+= 1
    now+= nn
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	while True:
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					if ind[i]+1 > N-2:
						ind[i] = -1
					else:
						ind[i] += 1

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						ind[target-1] += 1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			break

	for i in ind:
		if i != -1:
			print(-1)
			sys.exit()

	print(ans)



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

while A != [[0]] * N :
  #print([[0]] * N)
  finish = [0] * N
  for i in range(N):
    #print(A, i)
    if (A[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:
n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]
count=0
index=[0 for _ in range(n)]
match=0
max_match=n*(n-1)//2
flag=True
while(match!=max_match):
    s=set()
    for i in range(1,n+1):
        if index[i-1]!=n-1 and (not {i,A[i-1][index[i-1]]}&s):
            j = A[i-1][index[i-1]]
            if i==A[j-1][index[j-1]]:
                match+=1
                s|={i,j}
                index[i-1]+=1
                index[j-1]+=1
    if not s:
        flag = False
        break
    count+=1
print(count if flag else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(input())

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

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**5 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
N = int(input())
A = {}
for i in range(1,N+1):
    A[i] = deque(map(int,input().split()))
# print(A)

GAME = N*(N-1)//2
cnt = 0
ans = 0
cnt2 = 0
while cnt < GAME:
    ok = [True]*N
    cnt3 = 0
    for i in range(1,N+1):
        if cnt3 > N-1: break
        if A[i] and ok[i-1]:
            t = A[i][0]
            if ok[t-1] and A[t] and i == A[t][0]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                ok[i-1] = False
                ok[t-1] = False
                cnt3 += 2
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():    
    n = int(input())
    a = [deque(list(map(int,input().split()))) for _ in range(n)]
    ans = 0
    c = 0
    nn = n*(n-1)//2
    while True:
        pop_list = []
        pap = pop_list.append
        for i in range(n):
            for j in range(i+1,n):
                if a[i] and a[j]:
                    if a[i][0]-1 == j and a[j][0]-1 == i:
                        pap(i)
                        pap(j)
                        break
        if not pop_list:
            ans = -1
            break
        for i in pop_list:
            _ = a[i].popleft()
        c += len(pop_list)//2
        ans += 1
        if c == nn:
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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)
    a[i].append(0)
# print(a)
# print(now)

ans = 0
battle = 0
max_battle = n*(n-1)//2

for e in range(10**7):
    if battle == max_battle:
        break
    checked = [False]*n
    nogame = True
    for i in range(n):
        x = i
        y = now[i]
        if y < x:
            continue

        if checked[i] or checked[y] or now[i]==-1:
            continue
        checked[i] = True
        if now[y]==i:
            checked[y] = True
            now[x] = a[x].popleft()-1
            now[y] = a[y].popleft()-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 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 = tuple()
    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-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, )
                done_player_list += (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 = tuple()
        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):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
if len(candidate) == 0:
	print(-1)
	exit()
day = 0
while True:
	new_candidate = []
	go_next = False
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			if all([finish[p] for p in parent[e]]):
				new_candidate.append(e)
				go_next = True
	day += 1
	candidate = new_candidate
	if not go_next:
		break

all_finished = all(finish)
if all_finished:
	print(day)
else:
	print(-1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:


def main():
    n = int(input())
    ls = [[int(x) for x in input().split()] for _ in range(n) ]
    can = [0 for _ in range(n)]


    for i in range(n):
        can[i] = ls[i].pop()
    ans = 0
    while 1:
        if sum(can)==0:
            break
        flg = False
        for i in range(n):
            if can[i]==0:
                pass
            else:
                if can[can[i]-1]-1 ==i:
                    can[can[i]-1] = 0
                    can[i]=0
                    flg = True
        if flg == False:
            print(-1)
            exit()

        for i in range(n):
            if can[i]==0:
                if len(ls[i]) != 0:
                    can[i] = ls[i].pop()
        ans += 1
    print(ans)

if __name__ =="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

#N = list(map(int, input().split()))

import sys
def input():
	return sys.stdin.readline().strip()


N = int(input())
A = []
day = [0]*N
for i in range(N):
	A.append(deque(map(int, input().split())))
num = 0
i = 0
judge = 0
while True:
	judge += 1
	i = i % N
	if len(A[i]) > 0:
		j = A[i][0] - 1
		if len(A[j]) > 0:
			if A[j][0] == i + 1:
				A[i].popleft()
				A[j].popleft()
				shiai = max(day[i], day[j]) + 1
				day[i] = shiai
				day[j] = shiai
				num += 1
				judge = 0

	i += 1

	if judge >= N:
		break

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	while True:
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					ind[i] += 1
					if ind[i] > N-2:
						ind[i] = -1

					ind[target-1] += 1
					if ind[target-1] > N-2:
						ind[target-1] = -1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			break

	for i in ind:
		if i != -1:
			print(-1)
			sys.exit()

	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(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
for _ in range(total+1):
    for man in range(N):
        if progress[man] >= N-1:
            continue
        rival = A[man][progress[man]] - 1
        if battled[man] or battled[rival]:
            continue
        if A[rival][progress[rival]] - 1 == man:
            progress[man] += 1
            progress[rival] += 1
            battled[man], battled[rival] = True, True
            any_battle = True
            if progress[man] == N-2:
                finished += 1
            if progress[rival] == N-2:
                finished += 1
    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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(input())

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

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**6 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

idx = [0] * N
finished = [False] * N
days = 0
while True:
  if all(finished):
    print(days)
    exit()
  days += 1
  lst = []
  for i in range(N):
    if finished[i] == True:
      continue
    else:
      select = A[i][idx[i]]
      if A[select][idx[select]] == i:
        lst.append(i)
  for i in range(len(lst)):
    if idx[lst[i]] >= N-2:
      finished[lst[i]] = True
    idx[lst[i]] = min(idx[lst[i]]+1, N-1)
  if len(lst) == 0:
    print('-1')
    exit()

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())) for i in range(N)]

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

day_limit = N * (N - 1) // 2 + 1
for i in range(day_limit):
    for man_idx in range(N):
        if progress_list[man_idx] >= N - 1:
            continue
        opponent_idx = A[man_idx][progress_list[man_idx]] - 1
        if exhausted[opponent_idx]:
            continue

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

    if sum(exhausted) == 0:
        print(-1)
        exit()

    progress_list = [p + e for p, e in zip(progress_list, exhausted)]
    exhausted = [0] * N

    if all([progress >= N - 1 for progress in progress_list]):
        print(i + 1)
        exit()

else:
    print(-1)

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
        while True:
            f = True
            for a in A:
                if len(a) > 0:
                    f = False
            if f:
                break

            for i, a in enumerate(A):
                if len(a) == 0:
                    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(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

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

for _ in range(n):
    comp = list(map(int, input().split()))[::-1]
    game.append(comp)

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

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

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

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