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
input=sys.stdin.readline
import collections

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

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if gamed[i] > 0 or len(Q[i]) == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                b = True
                continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def topological_sort(root, links, in_count):
    topological = []
    q = root.copy()
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())

corr = {}
index = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        corr[i, j] = index
        corr[j, i] = index
        index += 1
match_count = n * (n - 1) // 2

roots = set()
in_links = [set() for _ in range(match_count)]
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = corr[i, j]
    roots.add(prev)

    for j in aaa[1:]:
        key = corr[i, j]
        out_links[prev].add(key)
        in_links[key].add(prev)
        prev = key

in_count = list(map(len, in_links))
roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

topological = topological_sort(roots, out_links, in_count)
if len(topological) != n * (n - 1) // 2:
    print(-1)
    exit()

ans = 0
depth = [0] * match_count

for v in topological:
    depth[v] = max(map(depth.__getitem__, in_links[v]), default=0) + 1

print(max(depth))

Submission status: Time Limit Exceeded

Solution code:
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-2 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    de.append([k[-1],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if sum(ppp) == -n:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != -1 and on[kkk[0]][ppp[kkk[0]]] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != -1 and ppp[kkk[0]] != -1 and on[kkk[1]][ppp[kkk[1]]] == kkk[0] and on[kkk[0]][ppp[kkk[0]]] == kkk[1]:
            de.append([on[kkk[1]][ppp[kkk[1]]],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][ppp[kkk[1]]],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][ppp[kkk[0]]],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

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

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

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if gamed[i] > 0 or len(Q[i]) == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] == 0 and len(Q[j]) > 0:
                if Q[j][0] == i+1:
#                    print("game:", j+1, i+1, days)
                    Q[i].popleft()
                    Q[j].popleft()
                    gamed[i] = 1
                    gamed[j] = 1
                    games -= 1
                    b = True
                    continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
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)]

# グラフつくる
graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
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

# トポロジカルソート
S = []
for v in range(N ** 2):
    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) != N ** 2:
    print(-1)
    exit()

seen = []


@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 range(N ** 2):
    ans = max(ans, dfs(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, *A = map(int, open(0).read().split())

t = list(np.array_split(A, N))

dayCount = 0
totalPlayCount = (N * (N - 1)) // 2
playCount = 0

while playCount < totalPlayCount:
    played = set()
    dayCount += 1
    player = 0
    todayPlayCount = 0
    for a in t:
        player += 1
        if player in played or a.size == 0:
            continue
        if t[a[0] - 1][0] == player and a[0] not in played:
            played.add(player)
            played.add(a[0])
            playCount += 1
            todayPlayCount += 1
            t[player - 1] = np.delete(a, 0, 0)
            t[a[0] - 1] = np.delete(t[a[0] - 1], 0, 0)

    if todayPlayCount == 0:
        print(-1)
        break

if playCount == totalPlayCount:
    print(dayCount)

Submission status: Time Limit Exceeded

Solution code:
import sys


def dfs(root, links, in_count):
    topological = []
    q = root.copy()
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())

corr = {}
index = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        corr[i, j] = index
        corr[j, i] = index
        index += 1
match_count = n * (n - 1) // 2

roots = set()
in_count = [0] * match_count
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = corr[i, j]
    roots.add(prev)

    for j in aaa[1:]:
        key = corr[i, j]
        out_links[prev].add(key)
        in_count[key] += 1
        prev = key

roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

topological = dfs(roots, out_links, in_count)
if len(topological) != n * (n - 1) // 2:
    print(-1)
    exit()

ans = 0
depth = [1] * match_count
for v in topological:
    d = depth[v] + 1
    for u in out_links[v]:
        depth[u] = max(depth[u], d)

print(max(depth))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def dfs(root, links, in_count):
    topological = []
    q = root.copy()
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())
lines = sys.stdin.readlines()

roots = set()
in_count = defaultdict(lambda: 0)
out_links = defaultdict(set)

for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    prev = i * n + j if i < j else j * n + i
    roots.add(prev)

    for j in aaa[1:]:
        j -= 1
        key = i * n + j if i < j else j * n + i
        out_links[prev].add(key)
        in_count[key] += 1
        prev = key

roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

topological = dfs(roots, out_links, in_count)
if len(topological) != n * (n - 1) // 2:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in out_links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
for i in range(10**5):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
        else:
            t += 1
    if t == N:
        break
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
if ans == 100000:
    print(-1)
    exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]

# circuit check
search = [c for c in candidate]
edge_copy = [[e for e in edge[i]] for i in range(M)]
parent_copy = [[p for p in parent[i]] for i in range(M)]
while len(search) > 0:
	s = search.pop()
	del_list = []
	for e in edge_copy[s]:
		parent_copy[e].remove(s)
		if len(parent_copy[e]) == 0:
			search.append(e)
			del_list.append(e)
	for e in del_list:
		edge_copy[s].remove(e)
if sum([len(parent_copy[i]) for i in range(M)]) > 0:
	print(-1)
	exit()

day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day)

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
    done = list(range(N))
    while True:
        used = [False] * N
        tmp_done = []
        for i in done:
            if not used[i] and p[i] < n:
                j = A[i][p[i]] - 1
                if not used[j] and p[j] < n and A[j][p[j]] - 1 == i:
                    used[i] = True
                    used[j] = True
                    p[i] += 1
                    p[j] += 1
                    tmp_done.append(i)
                    tmp_done.append(j)
        if len(tmp_done) == 0:
            for i in range(N):
                if p[i] < n:
                    print(-1)
                    return
            break
        done = tmp_done
        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]]"
    A = [list(map(int, input().split())) for i in range(N)]
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1.7):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()

Submission status: Time Limit Exceeded

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


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

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


print(solve())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [(i, 0) for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]

# circuit check
search = [c[0] for c in candidate]
edge_copy = [[e for e in edge[i]] for i in range(M)]
parent_copy = [[p for p in parent[i]] for i in range(M)]
while len(search) > 0:
	s = search.pop()
	del_list = []
	for e in edge_copy[s]:
		parent_copy[e].remove(s)
		if len(parent_copy[e]) == 0:
			search.append(e)
			del_list.append(e)
	for e in del_list:
		edge_copy[s].remove(e)
if sum([sum(parent_copy[i]) for i in range(M)]) > 0:
	print(-1)
	exit()

while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if depth[c] >= d:
		continue
	depth[c] = d
	finish[c] = True
	e = None
	for e in edge[c]:
		if depth[e] < d+1:
			candidate.append((e, d+1))
all_finished = all(finish)
if all_finished:
	print(max(depth) + 1)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = []
isAble = True
for i in range(N):
    A = list(map(int, input().split()))
    As.append(A)
pos = [0]*N
final = [N-1]*N
days = 0
isAble = True
while pos != final:
    days += 1
    s = []
    for i in range(N):
        if pos[i] != N-1:
            if i in s:
                pos[i] += 1
            else:
                b = As[i][pos[i]]-1
                if i == As[b][pos[b]]-1 and b not in s:
                    s.append(i)
                    s.append(b)
                    pos[i] += 1
    if len(s) == 0:
        isAble = False
        break
if isAble:
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import time
st = time.time()
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])
 
ans = 0
allpc = 0
stflag = False
while (True):
  if st -time.time() > 1.5:
    stflag = True
    break
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i].popleft()
      if aite not in tmpset:
        aiteaite = dic[aite].popleft()
        if aiteaite == i:
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
          allpc += 1
        else:
          dic[i].appendleft(aite)
          dic[aite].appendleft(aiteaite)
      else:
        dic[i].appendleft(aite)
 
  if playcount > 0:
    ans += 1
  else:
    break
if stflag:
  print(int(N * (N-1))//2)
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import time
st = time.time()
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])
 
ans = 0
allpc = 0
stflag = False
while (True):
  if time.time()-st > 1.9:
    stflag = True
    break
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i].popleft()
      if aite not in tmpset:
        aiteaite = dic[aite].popleft()
        if aiteaite == i:
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
          allpc += 1
        else:
          dic[i].appendleft(aite)
          dic[aite].appendleft(aiteaite)
      else:
        dic[i].appendleft(aite)
 
  if playcount > 0:
    ans += 1
  else:
    break
if stflag:
  print(int(N * (N-1))//2)
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
_match = {}
for i in range(N):
    _match[i + 1] = [int(j) for j in input().split(' ')]
 
all_match_count = N * (N-1) // 2
match = []
for p, lst in _match.items():
    result = []
    for t in lst:
        if p > t:
            result.append((t, p))
        else:
            result.append((p, t))
    match.append(result)
 
today_match = set()
already_finish = set()
result = 0
while True:
    could_make_match = False
    for i in range(N):
        try:
            c = match[i][0]
        except IndexError:
            continue
        if c in already_finish:
            match[i].pop(0)
            try:
                c = match[i][0]
            except IndexError:
                continue
        # 試合が見つかった
        if c in today_match:
            today_match.remove(c)
            already_finish.add(c)
            match[i].pop(0)
            could_make_match = True
        else:
            today_match.add(c)
        #print(today_match, already_finish)
    if not could_make_match:
        result = -1
        break
    result += 1
    #print('day' + str(result))
    today_match = set()
    if len(already_finish) == all_match_count:
        break
 
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import time
st = time.time()
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])
 
ans = 0
allpc = 0
stflag = False
while (True):
  if st -time.time() > 1.8:
    stflag = True
    break
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i].popleft()
      if aite not in tmpset:
        aiteaite = dic[aite].popleft()
        if aiteaite == i:
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
          allpc += 1
        else:
          dic[i].appendleft(aite)
          dic[aite].appendleft(aiteaite)
      else:
        dic[i].appendleft(aite)
 
  if playcount > 0:
    ans += 1
  else:
    break
if stflag:
  print(int(N * (N-1))//2)
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

Data = [[ 0 for i in range(N-1)]for j in range(N)]
Now = [ 0 for i in range(N)]
End = []

for i in range(N):
  Tmp = []
  Tmp = input().rstrip().split(' ')
  for j in range(N - 1):
    Data[i][j] = int(Tmp[j])

Cnt = 0
Flag = 0
while Flag == 0:
  Flag = 1
  Chk = [ 0 for i in range(N)]

  for i in range(N):
    nTmp = Now[i]
    if nTmp == N-1:
      continue
    if Chk[i] == 1:
      continue
    A = i + 1
    B = Data[i][nTmp]
    B -= 1
    nTmp2 = Now[B]
    TmpA = Data[B][nTmp2]
    if TmpA == A and Chk[B] == 0:
#      print(A)
      Flag = 0
      Now[i] += 1
      Now[B] += 1
      Chk[i] = 1
      Chk[B] = 1
      if Now[i]==N-1:
        End.append(i)
      if Now[B]==N-1:
        End.append(B)

  
  if Flag==0:
    Cnt += 1
  else:
    print(-1)
    sys.exit()
    break
  
#  print('cnt:%d' %(Cnt))
  

#  Flag = 1
  nLen = len(End)
  if nLen == N:
    Flag = 1
    break
#  for i in range(N):
#    if Now[i]!=N-1:
#      Flag = 0

print(Cnt)

Submission status: Time Limit Exceeded

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


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

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


print(solve())

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()
    from collections import deque
    A = [deque(map(int,input().split())) for _ in range(N)]
    days = 0


    desired = [ A[i][0] for i in range(N)]
    nextdesired = desired[:]
    while True:
        #print(A)
        
        firstgame = True

        
        # 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-1):
            
            a = desired[i]
            if a < 1:
                continue
            b = desired[a-1]

            if b == i+1:
                
                if len(A[a-1]) == 1:
                    A[a-1][0] = -1
                else:
                    A[a-1].popleft()
                
                if len(A[i]) == 1:
                    A[i][0] = -1
                else:
                    A[i].popleft()
                    
                desired[a-1] = -1
                nextdesired[i] = A[i][0]
                nextdesired[a-1] = A[a-1][0]

                # idxs[i] += 1
                # if idxs[i] == N-1:
                #     idxs[i] = N-2
                #     A[i][-1] = -1

                # desired[a-1] = -1
                # A[a-1][idxs[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
                    days += 1

                
        if firstgame:
            if desired.count(-1) == N:
                print(days)
                return
            else:
                print(-1)
                return
        desired = nextdesired[:]

            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n) for n in input().split() ] )

empty = [ [] for i in range(N) ]
default = [0 for i in range(N)]
day = 0
while(True):
    day += 1
    v = copy.deepcopy(default)
    for p in range(N):
        if len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if v[p] == 0  and  v[q] == 0  and  A[q][0]-1 == p:
            v[p] = 1
            v[q] = 1
            del A[p][0]
            del A[q][0]
        
    if A == empty:
        print(day)
        break
    
    if v == default:
        print(-1)
        break

Submission status: Time Limit Exceeded

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

Data = [[ 0 for i in range(N-1)]for j in range(N)]
Now = [ 0 for i in range(N)]

for i in range(N):
  Tmp = []
  Tmp = input().rstrip().split(' ')
  for j in range(N - 1):
    Data[i][j] = int(Tmp[j])

Cnt = 0
Flag = 0
while Flag == 0:
  Flag = 1
  Chk = [ 0 for i in range(N)]

  for i in range(N):
    nTmp = Now[i]
    if nTmp == N-1:
      continue
    if Chk[i] == 1:
      continue
    A = i + 1
    B = Data[i][nTmp]
    B -= 1
    nTmp2 = Now[B]
    TmpA = Data[B][nTmp2]
    if TmpA == A and Chk[B] == 0:
#      print(A)
      Flag = 0
      Now[i] += 1
      Now[B] += 1
      Chk[i] = 1
      Chk[B] = 1

  
  if Flag==0:
    Cnt += 1
  else:
    print(-1)
    sys.exit()
    break
  
#  print('cnt:%d' %(Cnt))
  

  Flag = 1
  for i in range(N):
    if Now[i]!=N-1:
      Flag = 0

print(Cnt)