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:
#!/usr/bin/env python3
import sys
import collections

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 and i not in matched:
                enemy = a[0] - 1
                if len(A[enemy]) > 0 and enemy not in matched:
                    enemy_enemy = A[enemy][0] - 1
                    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

def solve2(N: int, A: "List[List[int]]"):
    res = 0

    A = { i : collections.deque(a) for i,a in enumerate(A) }

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

        for k in del_keys:
            del A[k]

        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]]"
    solve2(N, A)

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 - 1):
            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}
                        match[i] += 1
                        match[vs] += 1
        if onmatch: day += 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 = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [0 for i in range(n)]
l1 = [0 for i in range(n)]
day = 0
count1 = 0
count2 = 0
key = 1
b = n*(n-1)//2
while count1 < b:
    for i in range(n-1):
        if l[i] < n-1 and l1[i] == 0:
            j = a[i][l[i]] - 1
            if l1[j] == 0 and l[j] < n-1:
                if a[j][l[j]] == i + 1:
                    count1 += 1
                    l[i] += 1
                    l[j] += 1
                    l1[i] = 1
                    l1[j] = 1
    if count1 > count2:
        day += 1
        count2 = count1
        l1 = [0 for i in range(n)]
    else:
        key = 0
        break
if key == 1:
    print(day)
else:
    print(-1)

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)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    for i in range(1, N + 1):
        if Ks[i]:
            continue
        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]]
        T = a * 10000 + b
        if T in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] += 1
            Cs[b] += 1
            tab.remove(T)
            wa.append(a)
            wa.append(b)
        else:
            tab.add(T)
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d += 1
    if c == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
sleep = [False] * N
An = [''] * N
deg = [0] * 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 [n for n in range(N) if fin[n]==False and sleep[n]==False]:
        if matched[n]:
            continue
        op = An[n][deg[n]]
        if matched[op - 1]:
            continue
        if An[op - 1][deg[op - 1]] == n + 1:
            flag = True
            matched[n] = True
            matched[op - 1] = True
            deg[n] += 1
            deg[op - 1] += 1
            sleep[op - 1] = False
            if deg[n] == N - 1:
                fin[n] = True
            if deg[op - 1] == N - 1:
                fin[op - 1] = True
        else:
            sleep[n] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])

ans = 0
while (True):
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i][0]
      if aite not in tmpset and dic[aite][0] == i:
        dic[i].popleft()
        dic[aite].popleft()
        tmpset.add(i)
        tmpset.add(aite)
        playcount += 1
  if playcount > 0:
    ans += 1
  if playcount == 0:
    break
failedflag = False
for i in range(1, N+1):
  if len(dic[i]) > 0:
    failedflag = True
    break
if failedflag:
  print(-1)
else:
  print(ans)

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]

    s = Counter()
    for i in range(1, N+1):
        if A[i-1]:
            d = A[i-1][-1]
            n = (min(i, d), max(i, d))
            s[n] += 1
    while True:
        c = 0
        dell = []
        adding = []
        for k, v in s.items():
            if v == 1:
                continue
            a, b = k
            A[a-1].pop()
            if A[a-1]:
                d = A[a-1][-1]
                n = (min(a, d), max(a, d))
                adding.append(n)
            A[b-1].pop()
            if A[b-1]:
                d = A[b-1][-1]
                n = (min(b, d), max(b, d))
                adding.append(n)
            dell.append(k)
            c += 1

        for k in dell:
            s.pop(k)
        for k in adding:
            s[k] += 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))

    # N = 1000
    # A = []

    # while True:
    #     for i in range(1, N+1):
    #         t = list(range(1, N+1))
    #         t.remove(i)
    #         random.shuffle(t)
    #         A.append(t)
    #     print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

def main():
    A_list = []
    if 'LOCAL' in os.environ:
        N = 1000
        for i in range(N):
            tmp = [j for j in range(N) if i != j]
            random.shuffle(tmp)
            A_list.append(tmp)

    else:
        N = _I()
        for i in range(N):
            A_list.append(LI())
        #  perr(A_list)
    new_A_list = []
    for A in A_list:
        new_A_list.append([i-1 for i in A])
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = [0 for i in range(N)]
    done_player_list = []
    position_sum = 0
    done_sum = (N-1)*N
    all_done_players = []
    while True:
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

        for i in range(N):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if i in done_player_list:
                continue

            if i in all_done_players:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list[i][current_position_list[i]]
            if opponent_idx in done_player_list:
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list[opponent_idx][current_position_list[opponent_idx]] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                done_player_list.append(opponent_idx)
                done_player_list.append(i)
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                if current_position_list[i] == N-1:
                    all_done_players.append(i)
                if current_position_list[opponent_idx] == N-1:
                    all_done_players.append(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

        if not is_ok:
            # 1試合も成立しなかったらストップする
            print(-1)
            exit()

        done_player_list = []
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r=[]
a=[]
b=[]
for i in range(n):
  r.append([int(i) for i in input().split()])
for i in range(n**2):
  k=[]
  f=[]
  for j in range(n):
    if len(r[j])!=0:
      p=r[j][0]-1
      if r[p][0]==j+1:
        if j+1 not in f:
          if p+1 not in f:
            k.append([r[j].pop(0),r[p].pop(0)])
            f.append(j+1)
            f.append(p+1)
  if len(k)==0:
    break
  else:
    for o in k:
      a.append(o)
    b.append(k)
if len(a)==(n*(n-1)//2):
  print(len(b))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
ans = 0
cur = [0] * n
while any(x < n - 1 for x in cur):
    ok = False
    used = [False] * n
    for i in range(n):
        if used[i] or cur[i] >= n - 1:
            continue
        j = a[i][cur[i]]
        if used[j] or cur[j] >= n - 1:
            continue
        if i == a[j][cur[j]]:
            ok = True
            cur[i] += 1
            used[i] = True
            cur[j] += 1
            used[j] = True
    if ok:
        ans += 1
    else:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    A = XLMIIS(N)
    days = 0
    idxs = [0] * N
    while True:
        #print(A)
        firstgame = True
        matched = False
        #desired = [ A[i][idxs[i]] for i in range(N)]
        desired = []
        for i in range(N):
            idx = idxs[i]
            l = A[i]
            #print(N,idx)
            desired.append(l[idx])
        #print(desired)

        if desired.count(-1) == N:
            print(days)
            return

        for i in range(N):
            a = desired[i]
            if a < 0:
                continue
            b = desired[a-1]
            if b < 0:
                continue
            # matched
            if b == i+1:
                # A[a-1].pop(0)
                # if len(A[a-1]) == 0:
                #     A[a-1].append(-1)
                # A[i].pop(0)
                # if len(A[i]) == 0:
                #     A[i].append(-1)
                # desired[a-1] = -1
                idxs[i] += 1
                if idxs[i] == N-1:
                    idxs[i] = N-2
                    A[i][-1] = -1
                desired[a-1] = -1
                idxs[a-1] += 1
                if idxs[a-1] == N-1:
                    idxs[a-1] = N -2
                    A[a-1][-1] = -1
                
                

                if firstgame:
                    firstgame = False
                    matched = True
                    days += 1
        if matched == False:
            print(-1)
            return 
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import copy

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

ind = [0 for i in range(n)]
ind_copy = copy.copy(ind)

# a = np.array(a)
# a = a - 1

ans = 0
while True:
    kanou = 0
    ans += 1
    for i in range(n):
        if ind[i] <= n-2:
            player = a[i][ind[i]]
        else:
            continue
        if ind[player-1] <= n-2:
            player_vs = a[player-1][ind[player-1]]
        else:
            continue
        if i == player_vs-1:
            kanou = 1
            ind_copy[i] = ind[i] + 1
            ind_copy[player-1] = ind[player-1] + 1
    if kanou == 0:
        hantei = 0
        for i in range(n):
            if ind[i] < n-2:
                hantei = 1
        if hantei == 1:
            ans = -1
        break
    ind = copy.copy(ind_copy)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
A = []

def intm1(a):
    return int(a) - 1

for _ in range(N):
    A.append(list(map(intm1, input().split())))

B = [0] * N

nokori = N*(N-1)
day = 0

while nokori > 0:
    day += 1
    ng = [False] * N
    upd = False
    for i in range(N):
        if ng[i] or B[i] == N-1:
            continue
        j = A[i][B[i]]
        if B[j] < N-1 and A[j][B[j]] == i and not ng[j]:
            ng[A[i][B[i]]] = True
            ng[A[j][B[j]]] = True
            B[i] += 1
            B[j] += 1
            upd = True
            nokori -= 2
    if not upd:
        break

print(day if nokori == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
ans = 0
all_match = sum(map(lambda x: len(x), A))
match_num = 0
while True:
    skip_list = set()
    for i, n in enumerate(A):
        if i in skip_list or len(n) == 0 or len(A[n[0]]) == 0 or n[0] in skip_list:
            continue
        if A[n[0]][0] == i:
            skip_list.add(A[n[0]].pop(0))
            skip_list.add(n.pop(0))
            match_num += 2
    if len(skip_list) == 0:
        print(-1)
        exit()
    ans += 1
    if all_match == match_num:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int, input().split())) for i in range(N)]
a=0
while A!=[0]*N:
    l=[]
    for i in range(N):
        if A[i]!=0:
            if A[A[i][0]-1][0]==i+1:
                l.append(i)
    if l==[]:
        print(-1)
        break
    else:
        for i in l:
            del A[i][0]
            if A[i]==[]:
                A[i]=0
    a+=1
else:
    print(a)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
a=[[]]
for i in range(n):
    ai = list(map(int,input().split()))
    a.append(ai)
ans=0
empty_lists=0
while(True):
    battled_i=[]
    for i in range(1,len(a)):
        if(len(a[i]) == 0):
            empty_lists+=1
            continue

        next_i = a[i][0]

        if(i in battled_i or next_i in battled_i):
            continue

        if(a[next_i][0] == i):
            del a[i][0]
            del a[next_i][0]
            battled_i.append(i)
            battled_i.append(next_i)

    if(empty_lists == n):
        break
    elif(len(battled_i) == 0):
        print(-1)
        sys.exit()

    battled_i.clear()
    empty_lists=0
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a_lists = [[] for _ in range(n+1)]
for i in range(n):
    a_lists[i + 1] = deque([int(j) for j in input().split()])


def solve():
    day = 0

    while True:
        done_list = []
        for i in range(1, n + 1):
            if len(a_lists[i]) == 0:
                continue
            a = a_lists[i][0]
            if len(a_lists[a]) == 0:
                continue
            b = a_lists[a][0]
            if b == i:
                done_list.append(i)

        if len(done_list) == 0:
            break;

        for d in done_list:
            a_lists[d].popleft()

        day += 1

    for a_list in a_lists:
        if len(a_list) != 0:
            return -1

    return day

print(solve())

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
  nagasa=[n-1]*n
  while True:
    m=[0]*n
    _c=c

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

      if m[i]!=0:
        continue

      if nagasa[i]!=0:
        a=l[i][-1]-1
        if m[a]!=0:
          continue

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

  return ans

# main()
print(main())

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
    cnt2 = 0
    flg = 1
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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()])

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r=[]
a=[]
b=[]
for i in range(n):
  r.append([int(i) for i in input().split()])
for i in range(n**3):
  k=[]
  f=[]
  for j in range(n):
    if len(r[j])!=0:
      p=r[j][0]-1
      if r[p][0]==j+1:
        if j+1 not in f:
          if p+1 not in f:
            k.append([r[j].pop(0),r[p].pop(0)])
            f.append(j+1)
            f.append(p+1)
  if len(k)==0:
    break
  else:
    for o in k:
      a.append(o)
    b.append(k)
if len(a)==(n*(n-1)//2):
  print(len(b))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  1 21:55:48 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)]
yesterday = [i for i in range(N)]

ans = 0
counta = 0
while counta < N:
    today = [True for i in range(N)]
    today_p = []
    for i in yesterday:
        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
                today_p.extend([i,vs])
    yesterday = today_p
#        print(i,vs,today,T)
    if len(today_p) == 0:
        ans = -1
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
table = [list(map(int, input().split())) for i in range(N)]
count = 0
while True:
  flag = 0
  game = [0]*N
  count += 1
  for i in range(N):
    if game[i] == 0 and len(table[i]) != 0:
      x = table[i][0]-1
      if game[x] == 0 and table[x][0] == i+1:
#        print(count,i,x)
        table[i].pop(0)
        table[x].pop(0)
        game[i] = 1
        game[x] = 1
        flag = 1
  if any(table) == 0:
    print(count)
    exit()
  if flag == 0:
    print(-1)
    exit()
print(count)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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


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


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)
# DAG の最長パスが答え

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())

e = [[] for _ in range(n)]
for i in range(n):
    a = map(int, input().split())
    for aa in a:
        aa -= 1
        e[i].append(aa)
# print(e)

inds = [0] * n
cur = [e[i][0] for i in range(n)]
# print(cur)
cnt = 0
while sum(cur) != -n:
    flg = False
    bls = [False] * n
    for ind, target in enumerate(cur):
        if bls[ind] or bls[target]:
            continue
        if cur[target] == ind:
            flg = True
            inds[ind] += 1
            inds[target] += 1
            bls[ind] = True
            bls[target] = True
            cur[ind] = e[ind][inds[ind]] if inds[ind] < n - 1 else -1
            cur[target] = e[target][inds[target]] if inds[target] < n - 1 else -1
    if not flg:
        print(-1)
        exit()
    cnt += 1
    # print(cur, cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]
count=0
match=0
flag=True
while(match!=n*(n-1)//2):
    s=set()
    for i in range(1,n+1):
        if (i not in s) and A[i-1] and (A[i-1][0] not in s):
            j = A[i-1][0]
            if i==A[j-1][0]:
                match+=1
                s|={i,j}
                A[i-1].pop(0)
                A[j-1].pop(0)
    if not s:
        flag = False
        break
    count+=1
print(count if flag else -1)

Submission status: Time Limit Exceeded

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

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

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