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())
A = []

for i in range(0, N):
    A.append([int(s) - 1 for s in input().split(" ")])

days = 0

while True:
    days = days + 1
    already = set()
    any = False
    for i in range(0, N):
        if i in already:
            continue

        already.add(i)
        if not A[i]:
            continue

        my = A[i][0]
        if my in already:
            continue

        rival = A[my][0]

        if rival == i:
            A[i].pop(0)
            A[my].pop(0)
            already.add(my)
            any = True

    if not any:
        days = -1
        break

    lens = [len(l) for l in A]
    if sum(lens) == 0:
        break

print(days)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [list(int(_) for _ in input().split()) for i in range(n)]
l = [i+[0] for i in l]
x = [0]*n
y = list(range(1,n+1))

for i in range(n*(n+1)+1):
    z = [l[ii][x[ii]] for ii in range(n)]
    if sum(z) == 0:
        print(i)
        break
    for ii in range(n):
        if z[z[ii]-1] == ii + 1:
            if x[ii] <= n - 3:
                x[ii] = x[ii]+1
            else:
                x[ii] = -1
    if i == n*(n+1):
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

vs_table = list()
for i in range(n):
    row = list(map(int, input().split()))
    vs_row = [(i, r - 1) for r in row]
    vs_row = deque(vs_row)
    vs_table.append(vs_row)

# print(vs_table)
schedule = set()


for i in range(n):
    schedule.add(vs_table[i].popleft())


ans = 0
while len(schedule) != 0:
    # print(schedule)
    schedule_rm = set()
    for sc in schedule:
        if (sc[1], sc[0]) in schedule:
            schedule_rm.add(sc)
            schedule_rm.add((sc[1], sc[0]))
    
    schedule = schedule - schedule_rm
    if len(schedule_rm) == 0:
        ans = -1
        break
    ans += 1

    for sc in schedule_rm:
        if len(vs_table[sc[0]]) != 0:
            schedule.add(vs_table[sc[0]].popleft())
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = []
fight = n * (n-1)

for i in range(n):
  s.append(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 enumerate(s):
    if s_pos[index] >= n-1:
      continue
    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 flag:
    if count >= fight:
      print(ans)
      break
    ans += 1
  else:
    print(-1)
    break

Submission status: Time Limit Exceeded

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

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

while (num < 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 (len(visit) == 0):
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

# check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
check = [0] * N #i番目の次の相手のindex

ans = 0
i = 0
tmp = 0
count = 0
while tmp < 2 * N + 5:
    if i % N == 0:
        ans += 1
        flag  = [True] * N #試合をしたかどうかチェック
        i = 0
    if check[i] >= N - 1:
        i += 1
        tmp += 1
        continue
    if flag[i] == False: #試合済みのとき
        i += 1
        tmp += 1
        continue
    b = A[i][check[i]]
    # print (b)
    if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1] == True: #試合できる時
        check[i] += 1
        check[b - 1] += 1
        flag[i] = False
        flag[b - 1] = False
        tmp = 0
        count += 1
    i += 1
    tmp += 1
    if count == (N * (N - 1))//2:
        break
    # print (check)

# print (check)
for i in check:
    if i != N - 1:
        print (-1)
        exit()

print (ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
plan=[None]*n
for i in range(n):
  p=list(map(int,input().split()))
  for j in range(len(p)):
    p[j]=p[j]-1
  plan[i]=p

# print(plan)
d=0
error=False
while True:
  d=d+1
#  print(str(d)+" day")
  done=[True]*n
  thisday=False
  for i in range(n):
    if done[i]==False:
      continue
    if len(plan[i])==0:
      continue
    target=plan[i][0]
    if done[target]==False:
      continue
    if len(plan[target])==0:
      continue
#    print("plan[i]")
#    print(plan[i])
#    print("target:"+str(target))
#    print("plan[target]")
#    print(plan[target])
    if plan[target][0]==i:
      # 試合を行う
#      print(str(i)+":"+str(plan[i][0])+" and "+str(target)+":"+str(plan[target][0])+ "fight!")
      plan[i].pop(0)
      plan[target].pop(0)
      done[i]=False
      done[target]=False
#      print("plan[i],plan[target] after that")
#      print(plan[i])
#      print(plan[target])
      thisday=True
  if thisday==False:
    # 試合が一つも組めなかった
    # ぜんぶからになっているなら正常終了　そうでなければ-1
    for i in range(len(plan)):
      if len(plan[i])!=0:
        error=True
    break
  
if error:
  print(-1)
else:
  print(d-1)

Submission status: Time Limit Exceeded

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

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

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

q = [k for k in Eb if Eb[k] == set()]
ans = 0
while q:
    qq = set()
    for k in q:
        for k2 in Ef[k]:
            qq.add(k2)
            Eb[k2].remove(k)
        Ef[k] = set()
    q = [k for k in qq if not Eb[k]]
    ans += 1
if sum(len(v) for v in Eb.values())>0 : ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def scheduler(N, A):
    days = 0
    while len([a for a in A if len(a)]):
        days += 1
        game = [0 for i in range(N)]
        for i in range(N):
            if len(A[i]):
                oppo = A[i][0] -1
                if A[oppo][0] - 1 == i:
                    game[i] = 1
        no_game = True
        for i in range(N):
            if game[i] == 1:
                del A[i][0]
                no_game = False
        if no_game:
            return(-1)
    return(days)


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

print(scheduler(N, A))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=deque([deque([int(_)-1 for _ in input().split()]) for __ in range(n)])
f=[0 for _ in range(n)]
m=n*(n-1)//2
d=0
while True:
    for i in range(n):
        if a[i] != deque([]):
            k=a[i][0]
            if f[i]==0 and f[k]==0:
                if a[k][0]==i:
                    f[i]=1
                    f[k]=1
                    m-=1
                    a[k].popleft()
                    a[i].popleft()
    if 1 not in f:
        print(-1)
        break
    else:
        f=[0 for _ in range(n)]
        d+=1
        if m==0:
            print(d)
            break

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]

    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    while True:
        had_game = False
        all_finish = True
        for i in range(N):
            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
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish:
            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

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) - 1 for a in input().split()] for _ in range(N)]

    #print(A)
    day = 0
    match = [0 for i in range(N)]

    #print(match)
    while True:
        onmatch = set()
        for i in range(N):
            if i not in onmatch and match[i] < N - 1:
                vs = A[i][match[i]]
                if match[vs] < N - 1:
                    if A[vs][match[vs]] == i and vs not in onmatch:
                        onmatch |= {i, vs}
        if onmatch:
            day += 1
            for i in onmatch: match[i] += 1
        else: break
    #print(match)

    for i in match[:N]:
        if i < N - 1:
            print(-1)
            break
    else: print(day)

    return 0

if __name__ == "__main__": solve()

Submission status: Time Limit Exceeded

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

memo = {}
cnt_max = {}
for i in range(n):
    cnt_max[i] = 0
for i in range(n):
    memo[i] = 0

set_ = set([i for i in range(n)])

cnt = 0
while True:
    flag = False
    set2 = set()
    for i in set_:
        if memo[i] == len(a[0]):
            set2.add(i)
            continue            
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            flag = True
            tmp = memo[i]
            max_1 = max(cnt_max[i], cnt_max[a[i][tmp] - 1])
            cnt_max[i] = max_1 + 1
            cnt_max[a[i][tmp] - 1] = max_1 + 1
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    for i in set2:
        set_.remove(i)
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
ans = 0
for i in cnt_max:
    ans = max(cnt_max[i] , ans)
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
    for i in range(1,N+1):
        if A[i]:
            t = A[i][0]
            if A[t] and i == A[t][0] and ok[i-1] and ok[t-1]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                ok[i-1] = False
                ok[t-1] = False
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

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

idx = [0] * N

ans = -1
q = list(range(N))
for day in range(N * (N - 1) // 2 + 1):
    # print("#", q, idx)
    if len(q) == 0: break
    elif sum(idx) == (N * (N - 1)):
        ans = day
        break
    #
    used = [False] * N
    q_tmp = []
    for src in q:
        if used[src] or (idx[src] >= N - 1): continue
        dst = A[src][idx[src]] - 1
        if used[dst] or (idx[dst] >= N - 1): continue
        #
        if A[dst][idx[dst]] - 1 == src:
            # print("##", src, dst)
            idx[src] += 1
            used[src] = True
            q_tmp.append(src)
            idx[dst] += 1
            used[dst] = True
            q_tmp.append(dst)
    q = list(q_tmp)
            
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= deque( [ int(x)-1 for x in sys.stdin.readline().split() ] )
#
tot= (n*(n-1))//2
now= 0
c= 0
while True:
    lst= []
    for i,ai in enumerate(a):
        if i in lst: continue
        if len(ai)==0: continue
        j  = ai[0]
        aj = a[j]
        if aj[0]==i:
            lst+= [ i,j ]
            now+= 1
    #
    if not lst: break
    for i in lst: a[i].popleft()
    #
    c+= 1
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print(-1)
                return
            else:
                raise ValueError("test")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if len(Q) == 0:
            print(count)
            return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

a = 0

cc = 0

ccc = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです
m = (N*(N-1))//2
for i in range(m):#周回
  btlf = [False for i in range(N)]#リセット
  ccc = 0
  for j in range(N):
    #print(idx)
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
        idx[a-1]+=1
        btlf[a-1] = True
        idx[j]+=1
        btlf[j] = True
        cc+=1
        ccc+=1
  if cc == m:#idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if ccc == 0:#対戦が一度もなければ打ち切ります
    break
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from sys import stdin


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, stdin.readline().rstrip().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  rev = 0
  while rev < N-1:
    dct = defaultdict(lambda:set([]))
    game = 0
    rev = N
    for i in range(N):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game,Pn[i],Pn[j] = [game+1,Pn[i]+1,Pn[j]+1]
          rev = min(rev,Pn[i],Pn[j])
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
plan=[None]*n
for i in range(n):
  p=list(map(int,input().split()))
  for j in range(len(p)):
    p[j]=p[j]-1
  plan[i]=p

d=0
error=False
while True:
  d=d+1
  done=[True]*n
  thisday=False
  for i in range(n):
    if done[i]==False:
      continue
    if len(plan[i])==0:
      continue
    target=plan[i][0]
    if done[target]==False:
      continue
    if len(plan[target])==0:
      continue
    if plan[target][0]==i:
      # match
      plan[i].pop(0)
      plan[target].pop(0)
      done[i]=False
      done[target]=False
      thisday=True
  if thisday==False:
    # no game today
    # check if every plan is finished
    for i in range(len(plan)):
      if len(plan[i])!=0:
        error=True
    break
  
if error:
  print(-1)
else:
  print(d-1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]

n1n = n*(n-1)

d = 0
for ii in range(n*n*2):
    co = 0
    i = 0
    F = [0 for i in range(n)]
    ga = 0
    while co < n:
        if F[i] == 0 and S[i] <= n-2:
            aite = A[i][S[i]]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
ans = 0
B = [True]*N
q = N
while q > 0:
    ans += 1
    p = True
    C = B[:]
    for i in range(N):
        if C[i] and C[A[i][-1]-1] and A[A[i][-1]-1][-1]-1 == i:
            A[A[i][-1]-1].pop()
            C[A[i][-1]-1] = False
            if len(A[A[i][-1]-1]) == 0:
                B[A[i][-1]-1] = False
                q -= 1
            A[i].pop()
            C[i] = False
            if len(A[i]) == 0:
                B[i] = False
                q -= 1
            p = False
    if p:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

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

  c=n*(n-1)
  ans=1
  while True:
    m=[0]*n
    _c=c

    for i in range(n):
      if c<=0:
        return ans

      if m[i]!=0:
        continue

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

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[-1,0]
while count!=n*(n-1)//2 and day<=10**5:
  if check[len(check)-2]==check[len(check)-1]:
    print(-1)
    sys.exit()
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check.append(count)
if day>10**5:
  print(-1)
  sys.exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
# ABC139
def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = A[x : x + N - 1][::-1]
    ans, flg, matched = 0, 0, set()
    while B:
        for i in list(B.keys()):
            if i in B and i not in matched:
                x = B[i][-1]
                if x in B and x not in matched and B[x][-1] == i:
                    B[i].pop(), B[x].pop()
                    matched |= {i, x}
                    flg = 1
                    if B[i] == []:
                        del B[i]
                    if B[x] == []:
                        del B[x]
        if flg:
            ans += 1
            flg, matched = 0, set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
    Costs=[INF]*N
    Costs[Start] = 0
    upd8s = [True]*N
    for i in range(2*N): #2N回ループ(負閉路の検出までみる)
        will_upd8s = [False]*N
        for s in range(N):
            if not upd8s[s]: continue    #前回更新してないので見ない
            for t,c in lines[s]:
                if c + Costs[s] < Costs[t]:
                    Costs[t] = Costs[s]+c
                    will_upd8s[t] = True #更新した点だけ次に見る
                    if i >= N:
                        return -INF

        if i == N-1: #Nループ目のGoalのCostを記録
            tmp = Costs[Goal]

        upd8s = will_upd8s[:]

    if tmp != Costs[Goal]:
        return -INF
    else:
        return Costs[Goal]


def calc(x,y):
    return x*(N-1) + y

N = inp()
AAA = [inpl() for _ in range(N)]


next = [[-1]*N for _ in range(N)]
for x in range(N):
    for y,A in enumerate(AAA[x]):
        next[x][A-1] = y

lines = defaultdict(set)
S = N*(N-1)+1
T = S + 1

for x in range(N):
    lines[S].add((calc(x,0),0))
    lines[calc(x,N-2)].add((T,0))
    for y in range(N-1):
        tx = AAA[x][y] - 1
        ty = next[tx][x]
        s = calc(x,y)
        lines[s].add((calc(tx,ty),0))
        if y != N-2:
            lines[s].add((calc(x,y+1),-1))

N = T+1
ret = -BellmanFord(S,T)

if ret == INF:
    print(-1)
else:
    print(ret+1)

Submission status: Time Limit Exceeded

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

P = [0] * n
is_possible = True
ans = 0

while is_possible:
    is_possible = False
    ans += 1
    W = {}

    for i in range(n):
        p = P[i]

        if p == n - 1:
            continue

        j = A[i][p] - 1

        if j in W and W[j] == i:
            is_possible = True
            P[i] += 1
            P[j] += 1
        else:
            W[i] = j

if max(P) == n - 1 and min(P) == n - 1:
    print(ans - 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

def f():
    day = 0
    ptrs = [0] * n

    while True:
        if all(ptr == n - 1 for ptr in ptrs):
            return day

        visited = set()
        ok = False
        for i in range(n):
            if ptrs[i] == n - 1 or i in visited:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if ptrs[x] == n - 1 or x in visited:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited.add(i)
                visited.add(x)
                ok = True

        # すべて未訪問の場合
        if not ok:
            return -1
        day += 1

print(f())

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[List[int]]"):
    flag = True
    counter = 0
    while flag:
        tmp = [a[0] for a in A]
        p_idx = []
        for i, t in enumerate(tmp):
            if i == tmp[t]:
                p_idx.append(i)
        if len(p_idx) == 0:
            print(-1)
            return
        for p in p_idx:
            A[p].pop(0)
            A[p].append(-1)
        if all([a[0] == -1 for a in A]):
            flag = False
        counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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)) - 1 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 sys
input = sys.stdin.readline

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

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[]
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1:
            #a[a[i][0]-1].pop(0)
            #a[i].pop(0)
            q.append(i)
            q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    if len(q)>0:
        for k in q:
            a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
idx = [0] * n

remain_games = n * (n-1) // 2
ans = 0
while remain_games:
    flag = [0] * n
    update = False
    for i in range(n):
        if idx[i] == n-1 or idx[ a[i][idx[i]] ] == n-1:
            continue

        b = a[i][idx[i]]
        if flag[i] == 0 and a[b][ idx[b] ] == i and flag[b] == 0:
            # b = a[i].popleft()
            # _ = a[b].popleft()
            idx[b] += 1
            idx[i] += 1
            flag[i] = 1
            flag[b] = 1
            remain_games -= 1
            # print(ans, i, b)
            update = True
    if not update:
        ans = -1
        break
    ans += 1

print(ans)