Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 100000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 200000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 300000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

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 1:
        gamed = [0 for _ in range(N)]
        x = 0
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
                x = 1
        days += 1
        if not x:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 400000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

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
    for _ in range(games):
        gamed = [0 for _ in range(N)]
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

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

x=[[[] for j in range(n)] for i in range(n)]

for i in range(n):
	t=[sorted([i,t-1]) for t in a[i]]
	#print(t)
	for j in range(n-2):
		x[t[j][0]][t[j][1]].append(t[j+1])
#print(x)


from collections import deque
dis=[[0 for _ in range(n)] for _ in range(n)]
que=deque([])

for i in range(n):
	tx=i
	ty=a[i][0]-1
	tx,ty=min(tx,ty),max(tx,ty)
	d=1
	dis[tx][ty]=1
	que.append((tx,ty,d))
while que:
	tx,ty,td=que.pop()
	dis[tx][ty]=max(dis[tx][ty],td)
	for ttx,tty in x[tx][ty]:
		que.append((ttx,tty,td+1))
	if td==(n*(n-1)//2+2):
		break
res=0
for t in dis:
	res=max(max(t),res)
print(res if res<=n*(n-1)//2 else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque

input = sys.stdin.readline

n = int(input())
a = [deque(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0


def check(p, q):
    if not len(a[p]) == 0:
        o = a[p][0]
        if a[o][0] == p:
            if p < o and not (p, o) in q:
                q.append((p, o))
            elif not (o, p) in q:
                q.append((o, p))

for p in range(n):
    check(p, q)

while len(q) > 0:
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)


for i in range(n):
    if not len(a[i]) == 0:
        print(-1)
        sys.exit()

print(day)

Submission status: Time Limit Exceeded

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

matched = [False] * N
for n in range(N):
    a = An[n][deg[n]] - 1
    b = An[a][deg[a]] - 1
    if b == n and matched[a] == matched[b] == False:
        set_ = tuple(sorted([a,b]))
        if set_ not in q:
            q.append(set_)
        matched[a] = True
        matched[b] = True

days = 0
while len(q):
    days += 1
    matched = [False] * N
    flag = False
    q_ = list(q)[:]
    q = deque([])
    for a, b in q_:
        if deg[a] < N - 2:
            deg[a] += 1
            c = An[a][deg[a]] - 1
            if An[c][deg[c]]-1 == a and matched[c] == False:
                set_ = tuple(sorted([a, c]))
                q.append(set_)
                matched[c] = True
        else:
            fin[a] = True
        if deg[b] < N - 2:
            deg[b] += 1
            d = An[b][deg[b]] - 1
            if An[d][deg[d]]-1 == b and matched[d] == False:
                set_ = tuple(sorted([b, d]))
                q.append(set_)
                matched[d] = True
        else:
            fin[b] = True

if False in fin:
    days = -1
print(days)

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 1:
        gamed = [0 for _ in range(N)]
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque
n = int(input())
a = [deque(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0


def check(p, q):
    if not len(a[p]) == 0:
        o = a[p][0]
        if a[o][0] == p:
            if p < o and not (p, o) in q:
                q.append((p, o))
            elif not (o, p) in q:
                q.append((o, p))

for p in range(n):
    check(p, q)

while len(q) > 0:
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)


for i in range(n):
    if not len(a[i]) == 0:
        print(-1)
        sys.exit()

print(day)

Submission status: Time Limit Exceeded

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

total=0
n=[0 for _ in l]
c=[False for _ in range(N)]
#end=[False for _ in range(N)]
while sum(n)<N*(N-1):
    total+=1
    check=[False for _ in range(N)]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if n[j]==N-1 or check[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            """
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
            """
    if flag:
        print(-1)
        exit()
print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

node_list = []

def get_key(a, b):
    if a > b:
        return (a << 10) + b
    else:
        return (b << 10) + a

def link(parent, child):
    child.prev[parent.hash] = parent

def main():

    table = {}

    for i in range(0, N):
        array = [int(v) - 1 for v in input().split(' ')]

        j = array[0]

        key0 = get_key(i, j)
        if not key0 in table:
            e = E(i, j)
            table[key0] = e
            node_list.append(e)
        p = table[key0]

        for k in range(1, len(array)):
            j = array[k]
            key = get_key(i, j)

            if not key in table:
                e = E(i, j)
                table[key] = e
                node_list.append(e)
            n = table[key]

            link(p, n)

            p = n

class E:
    def __init__(self, a, b):
        if a > b:
            self.hash = (a << 10) + b
        else:
            self.hash = (b << 10) + a

        self.prev = {}

main()    

days = 0
close_list = []
while len(node_list) > 0:
    days += 1
    open_list = []

    for n in node_list:
        if len(n.prev) == 0:
            close_list.append(n.hash)
        else:
            open_list.append(n)

    if len(close_list) == 0:
        print("-1")
        exit()

    for n in close_list:
        for o in open_list:
            if n in o.prev:
                o.prev.pop(n)

    node_list = open_list
    close_list.clear()

print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0
while True:
    C = [0]*N
    for i in range(N):
        if C[i] == 0 and B[i] != N-1:
            b = A[i][B[i]]
            if C[b] == 1:
                continue
            if A[b][B[b]] == i:
                B[i] += 1
                B[b] += 1
                C[i], C[b] = 1, 1
    if sum(C) == 0:
        break
    days += 1
print(days if sum(B) == N*(N-1) else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict


def topological_check(roots, out_links, in_counts):
    depth = {r: 1 for r in roots}
    q = deque(roots)
    while q:
        v = q.popleft()
        d = depth[v] + 1
        for u in out_links[v]:
            in_counts[u] -= 1
            if in_counts[u] == 0:
                depth[u] = d
                q.append(u)
    if any(in_counts.values()):
        return -1
    return max(depth.values())


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

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

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

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

roots = {r for r in roots if in_counts[r] == 0}
print(topological_check(roots, out_links, in_counts))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

dep = []

for i in range(N):

    dep.append([0] * N)


lis = []

for i in range(N):

    l1 = []

    for j in range(N):

        l1.append([])

    lis.append(l1)

A = []

for i in range(N):

    a = list(map(int,input().split()))
    A.append(a)

    for j in range(len(a)-1):

        lmi = min(i,a[j]-1)
        lma = max(i,a[j]-1)
        rmi = min(i,a[j+1]-1)
        rma = max(i,a[j+1]-1)

        lis[lmi][lma].append([rmi,rma])

Q = []

 
for i in range(N):

    if i + 1 == A[A[i][0]-1][0] and i + 1 < A[i][0]:
        Q.append([i,A[i][0]-1])
        dep[i][A[i][0]-1] = 1

#print (Q)
#print (lis)
flag = True
if len(Q) == 0:
    flag = False


ans = 1

while len(Q) > 0 and ans < N * (N-1) // 2 + 5:

    q = Q.pop(0)

    for nex in lis[q[0]][q[1]]:

        l = nex[0]
        r = nex[1]

        if dep[l][r] < dep[q[0]][q[1]] + 1:
            dep[l][r] = dep[q[0]][q[1]] + 1
            Q.append([l,r])

            ans = max(ans,dep[l][r])

if ans <= N * (N-1) // 2 and flag:
    print (ans)
else:
    print (-1)

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 1:
        gamed = [0 for _ in range(N)]
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                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
                continue
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

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

total=0
n=[0 for _ in l]
c=[False for _ in range(N)]
#end=[False for _ in range(N)]
end=c.copy()
while sum(n)<N*(N-1):
    total+=1
    check=c.copy()
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if end[j] or check[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
    if flag:
        print(-1)
        exit()
print(total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and table[j][cursor[j]] == i and j not in is_matched:
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

node_list = []

def get_key(a, b):
    if a > b:
        return (a << 10) + b
    else:
        return (b << 10) + a

def link(parent, child):
    child.prev[parent.hash] = parent

def main():

    table = {}

    for i in range(0, N):
        array = [int(v) - 1 for v in input().split(' ')]

        j = array[0]

        key0 = get_key(i, j)
        if not key0 in table:
            e = E(i, j)
            table[key0] = e
            node_list.append(e)
        p = table[key0]

        for k in range(1, len(array)):
            j = array[k]
            key = get_key(i, j)

            if not key in table:
                e = E(i, j)
                table[key] = e
                node_list.append(e)
            n = table[key]

            link(p, n)

            p = n

class E:
    def __init__(self, a, b):
        if a > b:
            self.hash = (a << 10) + b
        else:
            self.hash = (b << 10) + a

        self.prev = {}

main()    

days = 0
close_list = []
while len(node_list) > 0:
    days += 1
    open_list = []

    for n in node_list:
        if len(n.prev) == 0:
            close_list.append(n)
        else:
            open_list.append(n)

    if len(close_list) == 0:
        print("-1")
        exit()

    for n in close_list:
        for o in open_list:
            if n.hash in o.prev:
                o.prev.pop(n.hash)

    node_list = open_list
    close_list.clear()

print(days)

Submission status: Time Limit Exceeded

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

total=0
n=[0 for _ in l]
#c=[False for _ in range(N)]
end=[False for _ in range(N)]
while sum(n)<N*(N-1):
    total+=1
    check=[]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if end[j] or (j in check):
            continue
        tmp=l[j][n[j]]-1
        if  tmp in check:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            #check[j]=True
            #check[tmp]=True
            check.append(j)
            check.append(tmp)
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
    if flag:
        print(-1)
        exit()
print(total)

Submission status: Time Limit Exceeded

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

total=0
n=[0 for _ in l]
#c=[False for _ in range(N)]
end=[False for _ in range(N)]
while sum(n)<N*(N-1):
    total+=1
    check=[False for i in range(N)]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if end[j] or check[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
    if flag:
        print(-1)
        exit()
print(total)

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)]
        for i in range(N-1,-1,-1):
            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
                continue
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if table[j][cursor[j]] == i and j not in is_matched:
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

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)]
        for i in range(N-1):
            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
                continue
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

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

Submission status: Time Limit Exceeded

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

#N=4
#l=[[j for j in range(N)] for i in range(N)]

check=[[False if i!=j  else True for i in range(N)] for j in range(N)]
total=0
n=[0 for _ in l]
end=[False for _ in range(N)]
while sum(n)<N*(N-1):
    total+=1
    check=[False for i in range(N)]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if end[j] or check[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
    if flag:
        print(-1)
        exit()
print(total)

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
    L = [N-1 for _ in range(N)]

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(N-1):
            if gamed[i] > 0 or L[i] == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] > 0 or L[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
                L[i] -= 1
                L[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:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1:
      j = table[i][cursor[i]]
      if i not in is_matched and table[j][cursor[j]] == i and j not in is_matched:
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

Submission status: Time Limit Exceeded

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

#N=4
#l=[[j for j in range(N)] for i in range(N)]

check=[[False if i!=j  else True for i in range(N)] for j in range(N)]
total=0
n=[0 for _ in l]
end=[False for _ in range(N)]
while (all(end))==False:
    total+=1
    check=[False for i in range(N)]
    #print("n:",total)
    flag=True
    for j in range(N):
        #print("j:{}".format(j))
        if end[j]:
            continue
        tmp=l[j][n[j]]-1
        if  check[j] or check[tmp]:
            continue
        if j==l[tmp][n[tmp]]-1:
            flag=False
            n[j]+=1
            n[tmp]+=1
            check[j]=True
            check[tmp]=True
            if n[j]==N-1:
                end[j]=True
            if n[tmp]==N-1:
                end[tmp]=True
    if flag:
        print(-1)
        exit()
print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import time     #ズルです…
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    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
    aida = time.time()
    if aida-start > 1.9:
        print(N*(N-1)//2)       #ズル
        exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
ans = 0
tmp = 0
total = (N * (N - 1)) // 2

while True:
    sLst = [0] * N
    for j in range(N):
        if len(a[j]) != 0 and len(a[a[j][0] - 1]) != 0:
            if sLst[j] == 0 and sLst[a[j][0] - 1] == 0:
                if a[a[j][0] - 1][0] == j + 1:
                    sLst[a[j][0] - 1] = a[a[j][0] - 1].pop(0)
                    sLst[j] = a[j].pop(0)
                    tmp += 1
                    total -= 1
    if total == 0:
        ans += 1
        break

    if tmp == 0:
        print(-1)
        exit()

    tmp = 0
    ans += 1

print(ans)

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(N-1):
            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()