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=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
MATCH = n*(n-1)//2

def f(a, b):
    if a > b:
        a, b = b, a
    return a*(2*n-a-3)//2 + b - 1

a = [[set(), set()] for _ in range(MATCH)]

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

    for j in range(1, n-1):
        a[f(i, l[j]-1)][0].add(f(i, l[j-1]-1))
        a[f(i, l[j-1]-1)][1].add(f(i, l[j]-1))




day = 0
removed = 0
while True:
    remove_q = deque([])
    for i in range(MATCH):
        if a[i][0] == set():
            remove_q.append([i, a[i][1]])
            a[i][0].add(-1)

    day += 1
    if not remove_q:
        print(-1)
        exit()
    for r in remove_q:
        for i in r[1]:
            a[i][0].remove(r[0])
        removed += 1
    if removed == MATCH:
        print(day)
        exit()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        gamed = [0]*N # 選手がその日に試合済みかどうか
        tmp = [] # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if gamed[i] == 0 and opp[i] >= 0 and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.append(i)
                tmp.append(opp[i])
                gamed[i] = gamed[opp[i]] = 1
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

def check(li, cnt):
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    nxtli = set()
    for i in li:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をセットに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    return nxtli, cnt

cnt = N*(N-1)//2
li = set(range(1, N+1))
day = 0
while cnt > 0:
    li, cnt = check(li, cnt)
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

import sys

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 = [[]]
for i in range(N):
    A.append(LIST()[::-1])

def check(li):
    global cnt
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    nxtli = set()
    for i in li:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をセットに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    return nxtli

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    nxtli = check(nxtli)
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
days = 0  # 日数
taisen = []  # 対戦表
battle = []  # 対戦予定の入ったプレーヤ
T = [[[0, 0] for _ in range(N - 1)] for __ in range(N)]  # 残対戦リスト
_T = [[]for __ in range(N)]


def update(n):
    if T[n] != []:
        taisen.append(T[n].pop(0))


for n in range(N):
    _ = list(map(int, input().split()))
    for _n in range(N - 1):
        if _[_n] > n + 1:
            T[n][_n] = [n, _[_n]-1]
        else:
            T[n][_n] = [_[_n]-1, n]
    update(n)

while T != _T or taisen != []:
    for t in taisen[:]:  # 対戦表の中でこなせる試合を探して消化
        if taisen.count(t) == 2 and not (t[0] in battle) and not (t[1] in battle):
            battle.extend(t)
            taisen.remove(t)
            taisen.remove(t)
            update(t[0])
            update(t[1])
    if battle == []:
        print('-1')
        exit()
    days += 1
    battle = []
print(str(days))

Submission status: Time Limit Exceeded

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

import sys

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 = [[]]
for i in range(N):
    A.append(LIST()[::-1])

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = set()
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をセットに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

import sys

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 = [[]]
for i in range(N):
    A.append(LIST()[::-1])

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = set()
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をリストに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

import sys

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 = [[]]
for i in range(N):
    A.append(LIST()[::-1])

cnt = N*(N-1)//2
nxtli = list(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli[:]
    nxtli = []
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をリストに入れておく
                    nxtli += [i, a]
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-1] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now < 0:
                continue
            if now in already:
                continue
            if 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] = -1
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -1
                al_add(i)
                al_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:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=[]:
      que[i] = A[i-1].pop()
  fighted = []
  for i in range(1,N+1):
    if i not in fighted and que[i]!=0 and que[que[i]]==i:
      fighted.append(que[i])      
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

Submission status: Time Limit Exceeded

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



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

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      if len(An[i]) == 0:
        continue
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn = Qn | set([i,An[i][0]])        
        An[j].popleft()
        if len(An[j]) > 0:
          Qn = Qn | set([j,An[j][0]])        
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print(solve())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-1] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -2:
                continue
            if now in already:
                continue
            if 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] = -1
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -1
                al_add(i)
                al_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:
N = int(input())
A = []
for i in range(N):
    a = list(map(int, input().split(" ")))
    A.append(a)

prev = range(N)
day = 0
m = 0
while m  < (N * (N-1) // 2):
    #print("Day {}".format(day + 1))
    #print("==")
    m = 0
    matched = False
    played = []
    #print("prev {}".format(prev))
    for p in prev:
        if ((not (p in played)) and (A[p] != [])):
            #print("Checking {}".format(p))
            opp = A[p][0]-1
            if((not (opp in played)) and A[opp][0] == (p + 1)):
                #print("{} vs {}".format(p+1,opp+1))
                matched = True
                played.append(p)
                played.append(opp)
                A[p].pop(0)
                A[opp].pop(0)
                m = m + 1
                
    #print("{} matches played".format(m))
    if (not matched): # no matches made
        #print(A)
        for i in range(N):
            if (A[i] != []):
                print(-1)
                exit()
        break
    else:
        # go to next day
        day = day + 1
        prev = played
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import * 

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt = 0
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
ans = d if cnt == N*(N-1)//2 else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-2] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -3:
                continue
            if now in already:
                continue
            if 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] = -2
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -2
                al_add(i)
                al_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:
n = int(input())
li =[list(map(int,input().split())) for i in range(1,n+1)]

cnt = 0
check = []
kouho = list(range(1,n+1))
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in kouho:
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(i)
            check.append(temp)
    cnt += 1
    kouho = check.copy()
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

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

day=0
last_i=0
jyunban=[i for i in range(n)]
jyunban.insert(0,last_i)
match=[0 for i in range(n)]
while True:
  day+=1
  check=[True for i in range(n)]
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)

Submission status: Time Limit Exceeded

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

prev = range(N)
day = 0
m = 0
while m  < (N * (N-1) // 2):
    #print("Day {}".format(day + 1))
    #print("==")
    m = 0
    matched = False
    played = []
    #print("prev {}".format(prev))
    for p in prev:
        if ((not (p in played)) and (A[p] != [])):
            #print("Checking {}".format(p))
            opp = A[p][0]-1
            if((not (opp in played)) and A[opp][0] == (p + 1)):
                #print("{} vs {}".format(p+1,opp+1))
                matched = True
                played.append(p)
                played.append(opp)
                A[p] = A[p][1:]
                A[opp] = A[opp][1:]
                m = m + 1
                
    #print("{} matches played".format(m))
    if (not matched): # no matches made
        #print(A)
        for i in range(N):
            if (A[i] != []):
                print(-1)
                exit()
        break
    else:
        # go to next day
        day = day + 1
        prev = played
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-2] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already:
                continue
            if 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] = -2
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -2
                al_add(i)
                al_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:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-1] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already:
                continue
            if 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] = -1
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -1
                al_add(i)
                al_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:
# -*- 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
nxt = [[] for i in range(cnt+1)]
nxt[0] += list(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    for i in nxt[day]:
        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()
                    # 変更があった場所をリストに入れておく
                    nxt[day+1] += [i, a]
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

from collections import deque

N=int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
lencount = 0
ans = 0
while lencount < N:
    update = False
    done = [0]*N
    for i in range(N):
        if len(A[i]) == 0 or done[i] == 1: continue
        tmp = A[i][0]-1
        if len(A[tmp]) == 0 or done[tmp] == 1: continue
        if A[tmp][0]-1 == i:
            update = True
            done[i] = 1
            done[tmp] = 1
            A[i].popleft()
            A[tmp].popleft()
            if len(A[i]) == 0:
                lencount+=1
            if len(A[tmp]) == 0:
                lencount+=1
    ans += 1
    if not(update):
        print(-1)
        sys.exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=[]:
      que[i] = A[i-1].pop()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:
      que[que[i]] = 0      
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

Submission status: Time Limit Exceeded

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


def topological_sort(G, V):
    indeg = [0]*V   # 各頂点の入次数を記録。indeg[i]は頂点iの入次数を表す。
    for u in G:
        for v in u:
            indeg[v] += 1
    res = [0]*V        # ソート結果を記録
    idx = 0
    hq = [i for i in range(V) if indeg[i] == 0]  # 入次数0の頂点を格納
    while hq:  # 入次数0の頂点を除いたグラフの中で入次数0の点を探し、入次数0の点がなくなるまで繰り返す
        u = heapq.heappop(hq)   # 頂点番号の小さいものを優先
        res[idx] = u
        idx += 1
        for v in G[u]:
            indeg[v] -= 1       # uから辺が伸びていた先の頂点の入次数を1減らす
            if indeg[v] == 0:   # 入次数が0の点があればキューに入れる
                heapq.heappush(hq, v)
    # DAGでない場合はトポロジカルソート後にDPで最長経路を求める
    dp = [1]*V
    if idx == V:
        for i in res:
            for j in G[i]:
                dp[j] = max(dp[j], dp[i] + 1)
        return max(dp)
    else:
        return -1


N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
enID = [[0]*N for _ in range(N)]
ID = 0
for i in range(N-1):
    for j in range(i+1, N):
        enID[i][j] = ID
        enID[j][i] = ID
        ID += 1
V = N*(N-1)//2
G = [[] for _ in range(V)]
for i in range(N):
    for j in range(N-1):
        A[i][j] = enID[i][A[i][j]]
        if j == 0:
            continue
        else:
            G[A[i][j-1]].append(A[i][j])

print(topological_sort(G, V))

Submission status: Time Limit Exceeded

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

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

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        done = [False] * N
        schedule = []
        for i in q :
            j = A[i][0]
            if done[i] or done[j]:
                continue
                
            if i == A[j][0] :
                schedule.append(i)
                schedule.append(j)
                done[i] = done[j] = True
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())

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
nxtli = list(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli[:]
    nxtli = []
    for i in curli:
        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()
                    # 変更があった場所をリストに入れておく
                    nxtli += [i, a]
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)