Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

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


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0:
            t=al[j][0]-1
            if t not in ts and j not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    ts.add(j)
                    flg=False
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():    
    n = int(input())
    a = [list(reversed(list(map(int,input().split())))) for _ in range(n)]
    ans = 0
    f = []
    while True:
        pop_list = []
        pap = pop_list.append
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if a[i] and a[j]:
                    if a[i][-1]-1 == j and a[j][-1]-1 == i:
                        pap(i)
                        pap(j)
        if not pop_list:
            ans = -1
            break
        for i in pop_list:
            _ = a[i].pop(-1)
            if not a[i]:
                f.append(i)
        ans += 1
        if len(f) == n:
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
Ass = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
q = set([(i, 0) for i in range(N)])
idxs = [0] * N
n = 0
ans = 0
while q:
  nq = set()
  for i, k in q:
    a = i+1
    b = Ass[i][k]
    if a > b: a, b = b, a
    ct[(a, b)] += 1
    if ct[(a, b)] == 2:
      n += 1
      idxs[a-1] += 1
      if idxs[a-1] < N-1:
        nq.add((a-1, idxs[a-1]))
      idxs[b-1] += 1
      if idxs[b-1] < N-1:
        nq.add((b-1, idxs[b-1]))
  ans += 1
  q = nq
if n == N * (N-1) // 2:
  print(ans)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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:
  flag = False
  do_Flag = [False for i in range(n)]
  
  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 do_Flag[index] or do_Flag[a]:
      continue

    if b == index:
      s_pos[index] += 1
      s_pos[a] += 1
      do_Flag[a] = True
      do_Flag[index] = True
      flag = True
      count += 1
    
  if flag:
    if count >= fight:
      print(ans)
      break
    ans += 1
  else:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
import collections
plan = {}
for i in range(n):
    plan[i+1] = collections.deque(list(map(int, input().split())))

remain = [player for player in range(1,n+1)]
cnt = 0
while remain != []:
    visit = [p for p in remain]
    flag = True
    while visit != []:
        p_check = visit.pop()
        if plan[p_check][0] in visit and plan[plan[p_check][0]][0] == p_check:
            visit.remove(plan[p_check][0])
            plan[plan[p_check][0]].popleft()
            if len(plan[plan[p_check][0]]) == 0: remain.remove(plan[p_check][0])
            plan[p_check].popleft()
            if len(plan[p_check]) == 0: remain.remove(p_check)
            flag = False 
    if flag:
        cnt = -1
        break
    cnt += 1
print(cnt)

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

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです

for i in range((N*(N-1))//2):#周回
  btlf = [False for i in range(N)]#リセット
  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
        #c+=1#とりあえず試合数で実装して後から修正します
  if idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

ans = 0

def dfs():
    f = False
    s = set()
    for i in range(N):
        if len(L[i]) == 0:
            continue
        l = L[i].popleft()
        r = L[l].popleft()

        if i != r or l in s or r in s:
            L[i].appendleft(l)
            L[l].appendleft(r)
            continue

        s.add(l)
        s.add(r)
        f = True

    if f:
        global ans
        ans += 1
        dfs()

dfs()

le = max([len(v) for v in L])
if le == 0:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

from collections import deque

N = int(input())

A = [deque(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)
ans = 0
flg = 0

while flg == 0 :
    cnt = 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 :
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0

    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    else :
        ans = -1
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[List[int]]"):

    res = 0
    while any([len(a) > 0 for a in A]):
        matched = set()
        any_mached = False
        for i,a in enumerate(A): 
            if len(a) > 0:
                enemy = a[0] - 1
                if len(A[enemy]) > 0:
                    enemy_enemy = A[enemy][0] - 1
                    if i not in matched and enemy not in matched:
                        if i == enemy_enemy:
                            del A[i][0]
                            del A[enemy][0]
                            matched.add(i)
                            matched.add(enemy)
                            any_mached = True
        if not any_mached:
            res = -1
            break
        res += 1

    print(res)
    return


# Generated by 1.1.4 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)) 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:

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

for i in range(n):
    A[i].append(1010 + i)
    for j in range(n):
        A[i][j] -= 1

#print(A)

S = [0] * n

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:
        aite = A[i][S[i]]
        #print(S)
        #print("aite",aite)
        if aite <= 1000 and A[aite][S[aite]] == i and F[i] == 0 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 += 1
        if i == n:
            i = 0
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == (n-1)*n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
for day in range(ALL):
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

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

    opp = []
    for i in range(N):
        opp.append(A[i].pop(0)-1)
    # print(opp)
    count = 0
    matches = 0
    totmatch = N * (N-1)//2
    while matches != totmatch:
        count += 1
        update = []
        for i in range(N):
            if opp[i] != -1 and opp[opp[i]] == i:
                a, b = i, opp[i]
                # print(i, opp[i])
                opp[a], opp[b] = -1, -1
                # print(opp)
                update.append(a)
                update.append(b)
                matches += 1

        # print(opp)
        if len(update) == 0:
            return -1
        else:
            for i in update:
                if A[i]:
                    opp[i] = A[i].pop(0)-1
        # print(opp)
    return count


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    while True:
        t = []
        s = Counter()
        for i in range(1, N+1):
            if A[i-1]:
                n = (min(i, A[i-1][-1]), max(i, A[i-1][-1]))
                t.append(n)
                s[n] += 1

        c = 0
        for k, v in s.items():
            if v == 1:
                continue
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            c += 1
        if c == 0:
            break
        else:
            ans += 1

    for a in A:
        if a:
            return -1
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    bbb = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        bb = False
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            bb = True
                        else:
                            ls[i] = -1
                            bbb += 1
        if bbb == n:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ilist = [0] * n
days = 1
while True:
  booked = set()
  books = 0
  for i in range(n):
    if ilist[i] == n - 1:
      continue
    j = a[i][ilist[i]] - 1
    if a[j][ilist[j]] - 1 != i:
      continue
    if (i in booked) or (j in booked):
      continue
    books += 1
    booked.add(i)
    booked.add(j)
    ilist[i] += 1
    ilist[j] += 1
  if books == 0:
    print(-1)
    exit()
  if all(i == n - 1 for i in ilist):
    break
  days += 1
print(days)

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)]
    for i in range(N): 
        A[i].append(N)
        A[i].append(N)
    A.append([N for i in range(N + 1)])
    #print(A)
    day = 0
    match = [0 for i in range(N)]
    match.append(N)
    #print(match)
    while True:
        onmatch = set()
        for i in range(N):
            vs = A[i][match[i]]
            #print(vs)
            if A[vs][match[vs]] == i:
                if i not in onmatch 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:
# TLE
# n = int(input())

# a = [None for _ in range(n)]
# for i in range(n):
#     tmp = list(map(lambda a: int(a) - 1, input().split()))
#     a[i] = tmp
# indices = [0 for _ in range(n)]

# updated = True
# cnt = 0
# while updated:
#     updated = False
#     pops = []
#     for i in range(n):
#         if len(a[i]) == 0 or len(a[a[i][0]]) == 0:
#             continue
#         if i == a[a[i][0]][0]:
#             pops.append(i)
#     if len(pops) > 0:
#         updated = True
#         cnt += 1
#     for p in pops:
#         a[p].pop(0)
# valid = True
# for i in range(n):
#     if len(a[i]) > 0:
#         valid = False
#         break
# if valid:
#     print(cnt)
# else:
#     print(-1)


n = int(input())

a = [None for _ in range(n)]
for i in range(n):
    tmp = list(map(lambda a: int(a) - 1, input().split()))
    a[i] = tmp
indices = [0 for _ in range(n)]

updated = True
cnt = 0
while updated:
    updated = False
    pops = []
    for i in range(n):
        if indices[i] == n - 1:
            continue
        if i == a[a[i][indices[i]]][indices[a[i][indices[i]]]]:
            pops.append(i)
            updated = True
    if updated:
        cnt += 1
    for p in pops:
        indices[p] += 1
valid = True
for i in range(n):
    if indices[i] != n - 1:
        valid = False
        break
if valid:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n):
  l1=list(map(int,input().split()))
  l1=l1[::-1]
  l[i+1]=l1
b=True
day=0
while b and l!=[[] for i in range(n+1)]:
  day+=1
  todaygame=[]
  for i in range(1,n+1):
    if l[i]==[]:
      pass
    elif l[l[i][-1]]==[]:
      pass
    elif l[l[i][-1]][-1]==i:
      if not(i in todaygame) and not(l[i][-1] in todaygame):
        todaygame.append(i)
        todaygame.append(l[i][-1])
        del l[l[i][-1]][-1]
        del l[i][-1]
  if todaygame==[]:
    b=False
  else:
    todaygame=[]
if b:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

else:
    print(-1)

Submission status: Time Limit Exceeded

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

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
while(1):
    flag = 0
    match_array = [0] * N
    for i in range(N):
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
print(ans_date)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

ans = 0

def dfs():
    f = False
    s = set()
    for i in range(N):
        if len(L[i]) == 0:
            continue
        l = L[i].popleft()
        r = L[l].popleft()

        if i != r:
            L[i].appendleft(l)
            L[l].appendleft(r)
            continue

        if l not in s and r not in s:
            s.add(l)
            s.add(r)
            f = True
        else:
            L[i].appendleft(l)
            L[l].appendleft(r)

    if f:
        global ans
        ans += 1
        dfs()

dfs()

le = max([len(v) for v in L])
if le == 0:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
An = [''] * N
for n in range(N):
    An[n] = deque([int(x) for x in input().split()])

days = 0
while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in range(N):
        if fin[n] or matched[n]:
            continue
        op = An[n][0]
        if An[op - 1][0] == n + 1 and not matched[op - 1]:
            flag = True
            An[n].popleft()
            An[op - 1].popleft()
            matched[n] = True
            matched[op - 1] = True
            if len(An[n]) == 0:
                fin[n] = True
            if len(An[op - 1]) == 0:
                fin[op - 1] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[List[int]]"):
    ret = 0
    p = [0] * N
    n = N - 1
    while True:
        used = [False] * N
        found = False
        for i in range(N):
            if not used[i] and p[i] < n:
                j = A[i][p[i]]
                if not used[j] and p[j] < n and A[j][p[j]] == i:
                    used[i] = True
                    used[j] = True
                    p[i] += 1
                    p[j] += 1
                    found = True
        if not found:
            for i in range(N):
                if p[i] < n:
                    print(-1)
                    return
            break
        ret += 1
    print(ret)
    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)) - 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:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  1 20:25:02 2019

@author: Yamazaki Kenichi
"""

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

T = [0 for i in range(N)]
today = [True for i in range(N)]

ans = 0
counta = 0
while counta < N:
    today = [True for i in range(N)]
    for i in range(N):
        if today[i]:
            vs = A[i][T[i]] - 1
            if A[vs][T[vs]] == i + 1 and today[vs]:
                T[i] += 1
                T[vs] += 1
                if T[i] == N - 1:
                    T[i] = 0
                    counta += 1
                if T[vs] == N - 1:
                    T[vs] = 0 
                    counta += 1
                today[i], today[vs] = False, False
#        print(i,vs,today,T)
    flg = True
    for i in range(N):
        flg *= today[i]
    if flg :
        ans = -1
        break
    ans += 1
print(ans)

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()))[::-1] for _ in range(n)]
#print(*a, sep="\n")
opponent = [-1 for _ in range(n)]
match = 0
day = 0
while match < n*(n-1)//2:
	approved = False
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	#print(opponent)
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	#print(opponent)
	if not approved:
		print(-1)
		sys.exit()
	day += 1
print(day)

Submission status: Time Limit Exceeded

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

Cs = [0] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
while sw:
    tab = set()
    c = 0
    for i in range(1, N + 1):
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                break
            Cs[a] += 1
            Cs[b] += 1
        else:
            tab.add((a, b))
    if c == 0:
        d = 0
        break
    d += 1
print(d - 1)

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        bb = False
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            bb = True
                        else:
                            ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def main():    
    n = int(input())
    a = [list(reversed(list(map(int,input().split())))) for _ in range(n)]
    ans = 0
    while True:
        pop_list = []
        pap = pop_list.append
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if a[i] and a[j]:
                    if a[i][-1]-1 == j and a[j][-1]-1 == i:
                        pap(i)
                        pap(j)
        if not pop_list:
            ans = -1
            break
        _ = [a[i].pop(-1) for i in pop_list]
        ans += 1
        if not any(a):
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n):
  l1=list(map(int,input().split()))
  l1=l1[::-1]
  l[i+1]=l1
b=True
day=0
while b and l!=[[] for i in range(n+1)]:
  day+=1
  todaygame=[]
  for i in range(1,n+1):
    if l[i]==[]:
      pass
    elif l[l[i][-1]]==[]:
      pass
    elif l[l[i][-1]][-1]==i:
      if not(i in todaygame) and not(l[i][-1] in todaygame):
        todaygame.append(i)
        todaygame.append(l[i][-1])
        del l[l[i][-1]][-1]
        del l[i][-1]
  if todaygame==[]:
    b=False
  else:
    todaygame=[]
if b:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

else:
    print(-1)