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:
from collections import*
def main():
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d={}
    s=0
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,z=i,j
            if z<x:x,z=z,x
            x=x*n+z
            y,z=i,k
            if z<y:y,z=z,y
            y=y*n+z
            if not x in d:
                d[x]=s
                s+=1
            if not y in d:
                d[y]=s
                s+=1
            es+=(d[x],d[y]),
    e=[[]for _ in range(s)]
    for i,j in es:e[i]+=j,
    outs=defaultdict(list)
    ins=defaultdict(int)
    f=set(range(s))
    for i,j in es:
        outs[i].append(j)
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    while q:
        i=q.popleft()
        r+=i,
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
    if len(r)<s:
        print(-1)
        return
    data=[1]*s
    for i in r:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
from time import*
def main():
    start=time()
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d={}
    s=0
    es=[]
    for i,b in enumerate(a):
        for j,k in zip(b,b[1:]):
            x,z=sorted((i,j-1))
            x=x*n+z
            y,z=sorted((i,k-1))
            y=y*n+z
            if not x in d:
                d[x]=s
                s+=1
            if not y in d:
                d[y]=s
                s+=1
            es+=(d[x],d[y]),
    e=[[]for _ in range(s)]
    for v1,v2 in es:e[v1]+=v2,
    outs=defaultdict(list)
    ins=defaultdict(int)
    for v1,v2 in es:
        outs[v1].append(v2)
        ins[v2]+=1
    q=deque(v1 for v1 in range(s)if ins[v1]==0)
    res=[]
    while q:
        if time()-start>1.8:
            print(n*(n-1)//2)
            return
        v1=q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2]-=1
            if ins[v2]==0:
                q.append(v2)
    if len(res)<s:
        print(-1)
        return
    data=[1]*s
    for i in res:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
def main():
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d={}
    s=0
    es=[]
    for i,b in enumerate(a):
        for j,k in zip(b,b[1:]):
            x,z=sorted((i,j-1))
            x=x*n+z
            y,z=sorted((i,k-1))
            y=y*n+z
            if not x in d:
                d[x]=s
                s+=1
            if not y in d:
                d[y]=s
                s+=1
            es+=(d[x],d[y]),
    e=[[]for _ in range(s)]
    for v1,v2 in es:e[v1]+=v2,
    outs=defaultdict(list)
    ins=defaultdict(int)
    for v1,v2 in es:
        outs[v1].append(v2)
        ins[v2]+=1
    q=deque(v1 for v1 in range(s)if ins[v1]==0)
    res=[]
    while q:
        v1=q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2]-=1
            if ins[v2]==0:
                q.append(v2)
    if len(res)<s:
        print(-1)
        exit()
    data=[1]*s
    for i in res:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
(n,),*a=[list(map(int,t.split()))for t in open(0)]
d={}
s=0
es=[]
for i,b in enumerate(a):
    for j,k in zip(b,b[1:]):
        x,y=tuple(sorted((i,j-1))),tuple(sorted((i,k-1)))
        if not x in d:
            d[x]=s
            s+=1
        if not y in d:
            d[y]=s
            s+=1
        es+=(d[x],d[y]),
e=[[]for _ in range(s)]
for v1,v2 in es:e[v1]+=v2,
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(s)if ins[v1]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
if len(res)<s:
    print(-1)
    exit()
data=[1]*s
for i in res:
    t=data[i]+1
    for j in e[i]:
        if t>data[j]:data[j]=t
print(max(data))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
l=[]
for i in range(n):
  a=deque(list(map(int,input().split())))
  l.append(a)
num=0
exist=[i for i in range(n)]
while num>-1:
  pare=[]
  boo=[0]*n
  remove=[]
  for i in exist:
    if len(l[i])==0:
      remove.append(i)
      continue
    X=l[i][0]
    if boo[X-1]==1:
      continue
    if l[X-1][0]==i+1:
      boo[i]=1
      boo[X-1]=1
      pare.append((i,X-1))#インデックス
  for r in remove:
    exist.remove(r)
  if len(pare)==0:
    if len(exist)==0:
      break
    num=-1
    break
  for p in pare:
    l[p[0]].popleft()
    l[p[1]].popleft()
  num=num+1
print(int(num))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts [to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    max_d = 0
    stk = []
    stk.append((0,set(),0))
    while stk:
        nxt = []
        n,seen,d = stk.pop()
        res = -1
        if(n in seen):
            continue
        max_d = max(max_d,d)
        for x in gp[n]:
            nxt.append((x,seen.union(set([n])),d+1))
        stk = nxt+stk

    if(max_d==0):
        print(-1)
    else:
        print(max_d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(gp):
    max_d = 0
    stk = []
    stk.append((0,set(),0))
    while stk:
        nxt = []
        n,seen,d = stk.pop()
        res = -1
        if(n in seen):
            continue
        max_d = max(max_d,d)
        for x in gp[n]:
            nxt.append((x,seen.union(set([n])),d+1))
        stk = nxt+stk
    return max_d

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(gp)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(n,seen,gp,d):
    #print(d)
    res = -1
    if(n in seen):
        return -1
    for x in gp[n]:
        res = max(res,dfs(x,seen.union(set([n])),gp,d+1))

    if(res == -1):
        return d
    else:
        return res

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(0,set(),gp,0)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import *
import sys
import time

sys.setrecursionlimit(10**6)


#################### library ####################


#################### graph ####################

# graph: { node: [node] }
def is_cyclic(graph):
	for x0 in graph.keys():
		s = set()
		v = [x0]
		while v:
			x = v.pop()
			for y in graph[x]:
				if y not in s:
					s.add(y)
					v.append(y)
		if x0 in s:
			return True
	else:
		return False


#################### naive ####################


#################### process ####################

def read_input():
	N = int(raw_input())
	table = [ map(int, raw_input().split()) for _ in range(N) ]
	for k in range(N):
		for l in range(N-1):
			table[k][l] -= 1
	return table

def make_graph(table):
	N = len(table)
	dics = [ dict(zip(v, count())) for v in table ]
	graph = dict(((k, l), []) for k, l in combinations(range(N), 2))
	for k, l in graph.keys():
		i1 = dics[k][l]
		if i1 < N-2:
			j1 = table[k][i1+1]
			graph[(k, l)].append(min((k, j1), (j1, k)))
		i2 = dics[l][k]
		if i2 < N-2:
			j2 = table[l][i2+1]
			graph[(k, l)].append(min((l, j2), (j2, l)))
	return graph

def f():
	def calc_distance(v):
		if not graph[v]:
			return 0
		elif v in memo:
			return memo[v]
		else:
			dist = max(calc_distance(w)+1 for w in graph[v])
			memo[v] = dist
			return dist
	
	table = read_input()
#	table = [ [1,2], [0,2], [0,1] ]
	N = len(table)
	memo = { }
	graph = make_graph(table)
	if is_cyclic(graph):
		return -1
	return max(calc_distance(v) for v in combinations(range(N), 2)) + 1


#################### main ####################

print f()

Submission status: Time Limit Exceeded

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

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = list(map(list, set(map(tuple, q))))
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

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

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = q
    prevQ = get_unique_list(prevQ)
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
    for i,j in prevQ:
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

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

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = q.copy()
    prevQ = get_unique_list(prevQ)
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
    for i,j in prevQ:
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

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

num = int(input())
a_list = []

for i in range(num):
  a_list.append([int(s) for s in input().split()])
# print(a_list)
match_num = 0

while 1:
  # print('================ DAY'+str(match_num+1))
  done_flg = True
  impossible_flg = True
  
  head_list = []
  for lst in a_list:
    if len(lst) > 0:
      done_flg = False
      head_list.append(lst[0])
    else:
      head_list.append(0)
  
  if done_flg:
    print(match_num)
    break
    
  # print(head_list)
  
  for i in range(len(head_list)):
    if head_list[i] != 0:
      aite = head_list[i]
      if head_list[aite-1] != 0:
        if head_list[aite-1] == i+1:
          impossible_flg = False
          head_list[i] = 0
          head_list[aite-1] = 0
          # print(head_list)
          a_list[i].pop(0)
          a_list[aite-1].pop(0)
          # print(a_list)
  # print(a_list)
  
  if impossible_flg:
    print('-1')
    break
  
  match_num += 1

Submission status: Time Limit Exceeded

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

day = 0
while any(A):
    skip = []
    for i in range(n-1):
        if not A[i] or i in skip:
            continue
        vs = A[i][0]-1
        if i > vs or not A[vs] or vs in skip:
            continue
        if i == A[vs][0]-1:
            skip.append(i)
            skip.append(vs)
            A[i].pop(0)
            A[vs].pop(0)
    if not skip:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main(n, a):
    day = 0
    able = True
    flag = True
    while flag:
        day += 1
        tmp = False
        arr = []
        for p in range(n - 1):
            if len(a[p]) == 0 or p in arr or a[p][0] - 1 in arr:
                continue
            if a[a[p][0] - 1][0] - 1 == p:
                tmp = True
                arr.append(p)
                arr.append(a[p][0] - 1)
                a[a[p][0] - 1].pop(0)
                a[p].pop(0)
        if not tmp:
            flag = False
            able = False
        inFlag = False
        for p in range(n):
            if len(a[p]) > 0:
                inFlag = True
        if not inFlag:
            break


    if able:
        print(day)
    else:
        print(-1)

if __name__ == '__main__':
    n = int(input())
    a = [[int(i) for i in input().split()] for i in range(n)]
    main(n, a)

Submission status: Time Limit Exceeded

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

day = 0
while any(A):
    skip = []
    for i in range(n):
        if not A[i] or i in skip:
            continue
        vs = A[i][0]-1
        if not A[vs] or vs in skip:
            continue
        if i == A[vs][0]-1:
            skip.append(i)
            skip.append(vs)
            A[i].pop(0)
            A[vs].pop(0)
    if not skip:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys

input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a
    
import itertools 
def f():
    IDX = [0] * N
    day = 0
    end = 0
    for _ in itertools.cycle([None]):
        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:
N = int(input())
import sys

input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a
    
import itertools 
def f():
    IDX = [0] * N
    day = 0
    end = 0
    for _ in itertools.count():
        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:
#!/usr/bin/env python3


def solve(N, A):

    match_num = (N * (N-1)) // 2

    # リンク表
    subseq_matchs = dict()
    preced_count = dict()
    for i in range(2, N+1):
        for j in range(1, i):
            subseq_matchs[(i, j)] = []
            preced_count[(i, j)] = 0

    # 初期化
    for n in range(N):
        p1 = n + 1
        p2_preced = next(A[n])
        for p2_subseq in A[n]:
            pi, pj = max(p1, p2_preced), min(p1, p2_preced)
            si, sj = max(p1, p2_subseq), min(p1, p2_subseq)
            subseq_matchs[(pi, pj)].append((si, sj))
            preced_count[(si, sj)] += 1
            p2_preced = p2_subseq

    count0_matches = []
    for i in range(2, N+1):
        for j in range(1, i):
            if preced_count[(i, j)] == 0:
                count0_matches.append((i, j))

    match_count = 0
    for day in range(1, match_num+1):
        # print('day:', day, match_count)
        # 出来る試合がなければ失敗
        if not count0_matches:
            return -1
        next_count_0_matches = []
        # 一人のプレイヤーは一日一回しかプレイできない
        played = [False] * N
        for m in count0_matches:
            # print('  match:', m, idx_to_ij[m])
            if played[m[0]-1] or played[m[1]-1]:
                next_count_0_matches.append(m)
                continue
            # print(idx_to_ij[m][0], 'vs', idx_to_ij[m][1])
            played[m[0]-1] = True
            played[m[1]-1] = True
            # 次の試合のカウントを減らす
            # print('    subseq_matchs:')
            for sm in subseq_matchs[m]:
                # print('      ', sm, idx_to_ij[sm])
                preced_count[sm] -= 1
                if preced_count[sm] == 0:
                    next_count_0_matches.append(sm)
            match_count += 1
        # 全てのゲームを終えたら終了
        if match_count == match_num:
            return day
        count0_matches = next_count_0_matches


if __name__ == '__main__':
    N = int(input())
    A = []
    for _ in range(N):
        A.append((map(int, input().split())))

    ans = solve(N, A)

    print(ans)

Submission status: Time Limit Exceeded

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


def solve(N, A):

    def debug_info():
        print('------')
        for i in range(match_num):
            print(idx_to_ij[i], '=>', [idx_to_ij[j] for j in subseq_matchs[i]])
            print('  count:', preced_count[i])
        print([idx_to_ij[i] for i in count0_matches])

    # print('N', N)
    # print('A', A)
    match_num = (N * (N-1)) // 2
    subseq_matchs = [[] for _ in range(match_num)]
    preced_count = [0] * match_num

    # 変換表を先に作っておく
    ij_to_idx = dict()
    idx_to_ij = [0] * match_num
    idx = 0
    for i in range(2, N+1):
        for j in range(1, i):
            ij_to_idx[(i, j)] = idx
            ij_to_idx[(j, i)] = idx
            idx_to_ij[idx] = (i, j)
            idx += 1
    # print(ij_to_idx)
    # print(idx_to_ij)

    # 初期化
    for i in range(N):
        p1 = i + 1
        p2_preced = next(A[i])
        for p2_subseq in A[i]:
            preced_idx = ij_to_idx[(p1, p2_preced)]
            subseq_idx = ij_to_idx[(p1, p2_subseq)]
            subseq_matchs[preced_idx].append(subseq_idx)
            preced_count[subseq_idx] += 1
            p2_preced = p2_subseq

    # preced_count が 0 な物を探す
    count0_matches = []
    for i in range(match_num):
        if preced_count[i] == 0:
            count0_matches.append(i)
    # print(count0_matches)
    # debug_info()

    match_count = 0
    for day in range(1, match_num+1):
        # print('day:', day, match_count)
        # 出来る試合がなければ失敗
        if not count0_matches:
            return -1
        next_count_0_matches = []
        # 一人のプレイヤーは一日一回しかプレイでない
        played = [False] * N
        for m in count0_matches:
            # print('  match:', m, idx_to_ij[m])
            if played[idx_to_ij[m][0]-1] or played[idx_to_ij[m][1]-1]:
                # print('    played')
                next_count_0_matches.append(m)
                continue
            # print(idx_to_ij[m][0], 'vs', idx_to_ij[m][1])
            played[idx_to_ij[m][0]-1] = True
            played[idx_to_ij[m][1]-1] = True
            # 次の試合のカウントを減らす
            # print('    subseq_matchs:')
            for sm in subseq_matchs[m]:
                # print('      ', sm, idx_to_ij[sm])
                preced_count[sm] -= 1
                if preced_count[sm] == 0:
                    next_count_0_matches.append(sm)
            match_count += 1
        # 全てのゲームを終えたら終了
        if match_count == match_num:
            return day
        count0_matches = next_count_0_matches


if __name__ == '__main__':
    N = int(input())
    A = []
    for _ in range(N):
        A.append((map(int, input().split())))

    ans = solve(N, A)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - League

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

league = list()
day = 0
while True:
    clearCnt = 0
    for idx, ai in enumerate(a):
        i = idx + 1
        if len(ai) == 0:
            clearCnt += 1
            continue
        if i in league or ai[0] in league:
            continue
        else:
            enemyIdx = ai[0] - 1
            enemy = a[enemyIdx]
            if len(enemy) > 0 and enemy[0] == i:
                league.extend([i, ai[0]])
                ai.pop(0)
                a[idx] = ai
                enemy.pop(0)
                a[enemyIdx] = enemy
                
    if len(league) == 0:
        if clearCnt != n:
            day = -1
        break
        
    league.clear()
    day += 1

print(day)

Submission status: Time Limit Exceeded

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

allDone = False
day = 0
while allDone==False:
  allDone = True
  possible = False
  day += 1
  isDone = [False]*N
  for i in range(N):
    if len(A[i]) == 0:
      continue
    if isDone[i]==False:
      j = A[i][0]-1
      if len(A[j]) != 0 and isDone[j]==False:
        if A[j][0] == i+1:
          del A[i][0]
          del A[j][0]
          isDone[i] = True
          isDone[j] = True
          possible = True
          continue
        else:
          k = A[j][0]-1
          if len(A[k]) != 0 and isDone[k]==False:
            if A[k][0] == j+1:
              del A[k][0]
              del A[j][0]
              isDone[k] = True
              isDone[j] = True
              possible = True
              continue
          

  for n in range(N):
    if len(A[n]) != 0:
      allDone = False
  if possible == False:
    print(-1)
    exit()

print(day)

Submission status: Time Limit Exceeded

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

allDone = False
day = 0
while allDone==False:
  allDone = True
  possible = False
  day += 1
  isDone = [False]*N
  for i in range(N):
    if len(A[i]) == 0:
      continue
    if isDone[i]==False:
      j = A[i][0]-1
      if len(A[j]) != 0 and isDone[j]==False:
        if A[j][0] == i+1:
          del A[i][0]
          del A[j][0]
          isDone[i] = True
          isDone[j] = True
          possible = True
          continue

  for n in range(N):
    if len(A[n]) != 0:
      allDone = False
  if possible == False:
    print(-1)
    exit()

print(day)

Submission status: Time Limit Exceeded

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


allDone = False
day = 0
while allDone==False:
  allDone = True
  possible = False
  day += 1
  isDone = [False]*N
  for i in range(N):
    if len(A[i]) != 0 and isDone[i]==False:
      j = A[i][0]-1
      if len(A[j]) != 0 and isDone[j]==False:
        if A[j][0] == i+1:
          del A[i][0]
          del A[j][0]
          isDone[i] = True
          isDone[j] = True
          possible = True
          continue

  for n in range(N):
    if len(A[n]) != 0:
      allDone = False
  if possible == False:
    print(-1)
    exit()

print(day)

Submission status: Time Limit Exceeded

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


allDone = False
day = 0
while allDone==False:
  allDone = True
  day += 1
  isDone = [False]*N
  for i in range(N):
    if len(A[i]) != 0 and isDone[i]==False:
      j = A[i][0]-1
      if len(A[j]) != 0 and isDone[j]==False:
        if A[j][0] == i+1:
          del A[i][0]
          del A[j][0]
          isDone[i] = True
          isDone[j] = True
          continue

  possible = False
  for n in range(N):
    if isDone[n]:
      possible = True
  if possible == False:
    print(-1)
    exit()

  for n in range(N):
    if len(A[n]) != 0:
      allDone = False

print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
a = {i+1: list(map(int, input().split())) for i in range(n)}
 
ret = 1
while True:
    pair = []
    for k, v in a.items():
        if a[v[0]][0] == k:
            pair.append(k)
    for p in pair:
        if len(a[p]) > 1:
            a[p] = a[p][1:]
        else:
            a.pop(p)
    if len(a) == 0:
        break
    if len(pair) == 0:
        ret = -1
        break
    ret = ret + 1
 
print(ret)

Submission status: Time Limit Exceeded

Solution code:
# encodin: utf-8

N=int(input())
A=[list(map(lambda x: int(x)-1,  input().split())) for _ in range(N)]
#選手を0から採番したい

q = []
game = []

#iの次の組み合わせをキューに追加
def check(i):
    if len(A[i]) == 0:
        return

    #対戦相手
    j = A[i][0]

    if A[j][0] == i:
        game = [i, j] if i < j else [j, i] 
        if q.count(game) == 0:
            q.append(game) 

#初期化(第1試合のリスト)
for i in range(N):
    check(i)

day=0

prev_q = []
while len(q) > 0:
    day += 1

    prev_q = q
    q = []

    for game in prev_q:
        i = game[0]
        j = game[1]

        #消化した対戦を消す
        A[i].pop(0)
        A[j].pop(0)

        #試合をした人の次の試合をキューに積む
        check(i)
        check(j)

#対戦リストが残っちゃったら無理な組み合わせだった
for a in A:
    if len(a) > 0:
        print(-1)
        exit()

print(day)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8

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

day=0

print(len(A))

while len(A) > 0:
# for k in range(4):
    done=[]
    for i in range(N):
        print(i)
        if len(A[i]) == 0:
            print(len(A[i]))
            continue
        if done.count(i+1) == 0 and i + 1 == A[A[i][0]-1][0]:
            done.append(A[i][0])
            done.append(A[A[i][0]-1][0])
    print(done)
    for j in done:
        A[j-1].pop(0)
        print(A)
    day += 1

print(day)

Submission status: Time Limit Exceeded

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

day = 0
player_cnt = [0 for i in range(n)]
end_list = [[] for i in range(n)]

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

while a != end_list:
    player_flg = copy.copy(player_flg0)
    for i in range(n):
        if not a[i]:
            continue
        if a[a[i][0] - 1][0] == i + 1 and player_flg[i] == 0 and player_flg[a[i][0] - 1] == 0:
            tmp_num = a[i].pop(0)
            player_flg[i] += 1
            player_cnt[i] += 1
            a[tmp_num - 1].pop(0)
            player_flg[tmp_num - 1] += 1
            player_cnt[tmp_num - 1] += 1
    day += 1
    if player_flg == player_flg0:
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

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

day = 0
player_cnt = [0 for i in range(n)]
end_list = [[] for i in range(n)]

player_flg0 = [0 for i in range(n)]
player_flg1 = [1 for i in range(n)]

while a != end_list:
    player_flg = [0 for i in range(n)]
    for i in range(n):
        if not a[i] or player_flg == player_flg1:
            continue
        if a[a[i][0] - 1][0] == i + 1 and player_flg[i] == 0 and player_flg[a[i][0] - 1] == 0:
            tmp_num = a[i].pop(0)
            player_flg[i] += 1
            player_cnt[i] += 1
            a[tmp_num - 1].pop(0)
            player_flg[tmp_num - 1] += 1
            player_cnt[tmp_num - 1] += 1
    day += 1
    if player_flg == player_flg0:
        day = -1
        break
print(day)