Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

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

def f():
    IDX = [0] * N
    day = 0
    end = 0
    while 1:
        NEXT_IDX = IDX[:]
        flag = True
        for player, i in enumerate(IDX):
            #print(player, i)
            if i > N-2 or i == N-1:
                continue
            #print(player, i)
            enemy = A[player][i]

            if  A[enemy-1][IDX[enemy-1]] == player+1:
                NEXT_IDX[player] += 1
                flag = False
                #print(player, NEXT_IDX)
                if NEXT_IDX[player] == N-1:
                    end += 1
        if flag:
            #print(end, NEXT_IDX)
            return(-1)
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX[:]
print(f())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    N = int(input())
    A = []
    for i in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        row = [r - 1 for r in row]
        A.append(row)

    counter = [0] * (N + 1)
    finish = 0

    ans = 0
    check_done = set()
    while finish < N * (N - 1) // 2:
        checked = set()
        ans += 1

        exit_flg = True
        for n in range(N):
            # ある日程ですでにnは戦っている
            if n in checked:
                continue
            checked.add(n)

            # nの対戦は終了
            if counter[n] == N - 1:
                continue

            n_match = A[n][counter[n]]  # nの対戦相手
            n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相

            # nの対戦相手はある日の試合をすでに終えている
            if n_match in checked:
                continue

            # マッチング成立
            if n == n_match_match:
                exit_flg = False

                checked.add(n_match)

                finish += 1
                counter[n] += 1
                counter[n_match] += 1

        # 一つも組み合わせられなかった
        if exit_flg:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
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:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 100000:
      dp = [n-1]*n
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

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

from collections import Counter
from copy import deepcopy

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:
  new_idx = deepcopy(idx)
  if all(finished):
    print(days)
    exit()
  days += 1
  lst = []
  for i in range(N):
    if finished[i] == True:
      continue
    else:
      select = A[i][min(new_idx[i], N-1)]
      #print(i, select, new_idx[select], A[select][new_idx[select]], lst, idx)
      if A[select][new_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)
  #print(days, idx, finished)
  if new_idx == idx:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

res = 0
cnt = 0
pcnt = [N-1]*N
while cnt < (N*(N-1))//2:
    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
        else:
            continue
    if cnt == prev:
        res = -1
        break
    else:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

cnt = N*(N-1)//2
flag = 1
days = 0
while flag:
  flag = 0
  used = [False]*N
  for i in range(N):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] == False:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] == False:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = True
        used[numIND] = True
        flag = 1
        cnt -= 1
  else:
    if flag == 1:
      days += 1
#print(a)
#print(cnt)
if cnt != 0:
  print(-1)
else:
  print(days)

Submission status: Time Limit Exceeded

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

td = []
ans = 0
skip = 0
execflg = False
while 1:
        for idx, val in enumerate(A):
                if not val:
                        skip += 1
                        continue
                oppidx = val[0] - 1
                opp = A[val[0] - 1][0]
                if idx in td or oppidx in td:
                        continue
                
                if opp == idx + 1:
                        execflg = True
                        A[idx].pop(0)
                        A[oppidx].pop(0)
                        td.append(idx)
                        td.append(oppidx)
        else:
                if execflg:
                        td=[]
                        ans += 1
                        execflg = False
                        skip = 0
                else:
                        if skip == N:
                                print(ans)
                        else:
                                print(-1)
                        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    battle = [True]*N
    next_battle = battle[:]

    day = -1
    g = Graph(N)

    while True:
        day += 1
        flag = False

        battle[:] = next_battle
        for i, h in enumerate(a_head):
            # print(battle)
            if h == N-1:
                continue
            if battle[i] == True:
                next_battle[i] = False
            else:
                continue
            # print("day:{}, {}, {}".format(day+1, i+1, A[i][h]-1))
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True

                next_battle[i] = True
                next_battle[A[i][h]-1] = True
                # g.E[A[i][h]-1].remove(i)
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

import time

st = time.time()

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

# グラフつくる
nodes = set()
sources = set()
graph = defaultdict(list)
ins = defaultdict(int)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.add(a * N + b)

        nodes.add(a * N + b)
        nodes.add(c * N + d)

# トポロジカルソート
S = []
for v in sources:
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != len(nodes):
    print(-1)
    exit()

seen = []


@lru_cache(maxsize=None)
def dfs(v):
    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC139e
import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

day = 0
#print(a)
while (True):
    l = set()
    for i in range(n):
        if (len(a[i])!=0 and len(a[a[i][0] - 1])!=0 and a[a[i][0] - 1][0]-1 == i):
            l.add(i)
    if (len(l) == 0):
        break
    for i in l:
        a[i].popleft()
    #print(l)
    l.clear()
    day += 1
    #print(a)
count=0
for i in range(n):
    count += len(a[i])
if(count==0):
    print(day)
else:
    print(-1)

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
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
    battled = [False]*N
    for p in progress:
        if p < N-1:
            break
    else:
        print(day)
        break
    day += 1
    if not any_battle:
        print(-1)
        break
else:
    print(-1)

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,sumsiai=0,0
end=n*(n-1)//2
nex,minusnex=0,0
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]]
        minusnex=nex-1
        if i+1==a[nex-1][now[minusnex][0]] and now[minusnex][1] != day:
            siaisuu+=1
            now[i][0]+=1
            now[i][1],now[minusnex][1]=day,day
            now[minusnex][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

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

day = 0
ok = 1
count = (N * (N - 1)) // 2
can = 1
while True:
    if not ok:
        day = -1
        print('ok')
        break
    if count == 0:
        break
    if can == 0:
        day = -1
        break
    played = [0] * (N + 1)
    k = 1
    end_day = 0
    can = 0
    while True:
        if len(op[k]) > 0:
            opponent = op[k][0]
            if len(op[opponent]) > 0:
                if op[opponent][0] == k:
                    if played[k] == 0 and played[opponent] == 0:
                        count -= 1
                        can = 1
                        op[k].popleft()
                        op[opponent].popleft()
                    played[k] = 1
                    played[opponent] = 1
                    k = 1
                    while played[k] == 1:
                        k += 1
                        if k >= N:
                            day += 1
                            end_day = 1
                            break
                else:
                    played[k] = 1
                    if played[opponent] == 0:
                        k = opponent
                    else:
                        k = 1
                        while played[k] == 1:
                            k += 1
                            if k >= N:
                                day += 1
                                end_day = 1
                                break
            else:
                ok = 0
                break
        else:
            played[k] = 1
            k = 1
            while played[k] == 1:
                k += 1
                if k >= N:
                    day += 1
                    end_day = 1
                    break
        if end_day == 1:
            break

print(day)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = [[0]*(N-1)]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
    
B = [0]*N

hoge = 0
siai = 0
ans = 0
while siai < N*(N-1)/2:
    count = 0
    for i in range(N):
        if not len(A[i]) == 0 and not len(A[A[i][0]-1]) == 0 and A[A[i][0]-1][0]-1 == i:
            hoge = A[i][0]-1
            A[hoge].pop(0)
            A[i].pop(0)
            siai += 1
            count += 1
            if B[i] < B[hoge]:
                B[hoge] += 1
                B[i] = B[hoge]
            else:
                B[i] += 1
                B[hoge] = B[i]
    if count == 0:
        ans = -1
        break
    
            
if ans == 0:
    for i in range(N):
        if B[i] > ans:
            ans = B[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
li=[list(map(int,input().split())) for i in range(n)]
np_list=np.array(li).T
li=[0 for i in range(n)]
day=0

while(True):
  if sum(li)==n*len(np_list):
    print(day)
    break
  charange=[]
  for i in range(n):
    if li[i]<len(np_list):
      charange.append(np_list[li[i],i]-1)
    else:
      charange.append(-1)
  #charange=[np_list[li[i],i]-1 for i in range(n)]
  count=0
  for i in range(len(charange)):
    if charange[charange[i]]==i:
      count+=1
      li[i]+=1
      li[charange[i]]+=1
      charange[i]=-1
  if count==0:
    print(-1)
    break
  else:
    day+=1

Submission status: Time Limit Exceeded

Solution code:
def is_empty(a_list):
    for item in a_list:
        if item != []:
            return False
    return True


def process_league(a_list):
    done = set()
    clear = False
    for i in range(len(a_list)):
        if a_list[i] == []:
            continue
        else:
            if a_list[a_list[i][0]-1][0] == i + 1:
                if not (a_list[i][0] in done) and not (i+1 in done):
                    done.add(a_list[i][0])
                    done.add(i+1)
                    a_list[a_list[i][0]-1].pop(0)
                    a_list[i].pop(0)
                    clear = True

    return clear


n = input()
n = int(n)

a_list = []

for i in range(n):
    tmp_str = input()
    tmp_str_list = tmp_str.split(" ")
    for j in range(len(tmp_str_list)):
        tmp_str_list[j] = int(tmp_str_list[j])
    a_list.append(tmp_str_list)


days = 0

while(True):
    if is_empty(a_list):
        break
    days += 1
    result = process_league(a_list)
    if not result:
        days = -1
        break

print(days)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
s=[0 for i in range(n)]
ans=0
f=0
while f < n*(n-1)//2:
  c=[0 for i in range(n)]
  ans+=1
  for i in range(n):
    if c[i] == 0 and s[i] < n-1 :
      x=a[i][s[i]]-1
      y=s[x]
      if c[x]==0 and a[x][y] - 1 == i:
        c[i]=1
        c[x]=1
        s[x]+=1
        s[i]+=1
        f+=1
  if sum(c)==0:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

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

i = 0
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: #対戦可能な場合対戦。
      if (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
  #for i in range(N):#whileのおわる条件
    #if A[i] == []:
      #A[i] = 0
  #print(Q, A)
  #print(finish)
  if finish == [0]*N: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
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:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 300000:
      dp = [n-1]*n
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
alist = []
for i in range(n):
    alist.append(list(map(int, input().split())))

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    a = [int(x) for x in input().split()]
    for j in range(1,N):
        A[i][a[j-1]] = j

date = 0
match = 0
OK = True
while match < N*(N-1)//2:
    temp = set()
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[i][j] == A[j][i] == 1:
                temp.add(i)
                temp.add(j)
                match += 1
    if temp == set():
        OK = False
        break
    for i in temp:
        A[i] = list(map(lambda x: x-1, A[i]))
    date += 1

if OK:  print(date)
else: print(-1)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count):
    count = 0
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

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)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

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
while battle < max_battle:
    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:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))
    I = [0 for _ in range(N)]
    I = {j:0 for j in range(1,N+1)}
    res = 0
    while I:
        B = {j:A[j-1][i] for j,i in I.items()}
        checked = False
        for j in B:
            if B[B[j]] == j:
                if I[j] < N-2:
                    I[j] += 1
                else:
                    I.pop(j)
                checked = True
        if checked:
            res += 1
        elif B:
            res = -1
            break
    
    return str(res)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=0
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if taisenzumi[i]:continue
		if data[i]:
			aite=data[i][0]
			# print(data[i],aite)
			if taisenzumi[aite-1]:continue
			# print(data[i],aite)
			if data[aite-1][0]==i+1:
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=1
			else:continue
	if not flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
ans = 0
pos = [0] * n

while any([(n - 1) - x for x in pos]):
    pos_check = [False] * n
    checker = True
    for i in range(n):
        for j in range(i + 1, n):
            if pos[i] == n - 1 or pos[j] == n - 1:
                continue
            if a[i][pos[i]] == j + 1 and a[j][pos[j]] == i + 1:
                pos_check[i] = True
                pos_check[j] = True
    for i in range(n):
        if pos_check[i]:
            pos[i] += 1
            checker = False
    if checker:
        print(-1)
        sys.exit()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = {}
fight = n * (n-1)

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


ans = 1
count = 0
s_pos = [0 for i in range(n)]

while True:
  do_Flag = []
  flag = False
  for index, x in s.items():
    a = x[s_pos[index]] - 1
    b = s[a][s_pos[a]] - 1
    if b == index:
      count += 1
      do_Flag.append(index)
      flag = True
  
  for i in do_Flag:
    s_pos[i] += 1
    if s_pos[i] >= n-1:
      s.pop(i)
  
  if flag:
    if count >= fight:
      print(ans)
      break
    ans += 1
  else:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    for _ in range(N):
        A.append(list(map(int,input().split())))
    # next_pos = [A[i].pop(0) for i in range(N)]
    next_pos = []
    for i in range(N):
        next_pos.append(A[i].pop(0))
    ans = 0
    # check = [0 for _ in range(N)]
    check = []
    for _ in range(N):
        check.append(0)
    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:
from collections import deque

import sys
input = sys.stdin.readline


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

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
                    if num >= n * (n - 1) // 2:
                        print(day)
                        exit()
    if (len(visit) == 0):
        print(-1)
        exit()
    if num >= n * (n - 1) // 2:
        print(day)
        exit()

Submission status: Time Limit Exceeded

Solution code:
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

while flg == 0 :
    cnt = 0
    cnt2 = 0
    flg = 1
    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)