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
def input():
    return sys.stdin.readline()

def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False

    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False
        # print(l, ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N=int(input())

A=[[int(i) for i in input().split()] for _ in range(N)]
l=[0 for _ in range(N)]
ll=[0 for _ in range(N)]
r=[i for i in range(N)]
rr=[i for i in range(N)]
day=0
for _ in range(10**9):
    if r==[]:
        can=True
        break
    can=False
    for i in r:
        j=A[i][l[i]]-1
        if A[j][l[j]]-1==i:
            ll[i]+=1
            can=True
            if ll[i]==N-1:
              rr.remove(i)
    l=deepcopy(ll)
    r=deepcopy(rr)
    if can==False:
        break
    day+=1
if can==False:
    print(-1)
if can==True:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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
        elif c in already_finish:
            match[i].pop(0)
        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:
import sys
readline = sys.stdin.readline
from collections import deque
N = int(readline())
G = [[] for i in range(N*N)]
deg = [0]*(N*N)
day = [0]*(N*N)
F = set()
for p in range(N):
    *A, = map(int, readline().split())
    for k in range(N-1):
        A[k] -= 1
    prv = A[0]+p*N if A[0] < p else p+A[0]*N
    F.add(prv)
    for k in range(1, N-1):
        i = A[k]+p*N if A[k] < p else p+A[k]*N
        G[prv].append(i)
        deg[i] += 1
        prv = i
que = deque()
for i in F:
    if deg[i] == 0:
        que.append(i)
        day[i] = 1
rest = N*(N-1)//2
while que:
    v = que.popleft()
    rest -= 1
    d = day[v]
    for w in G[v]:
        deg[w] -= 1
        if deg[w] == 0:
            day[w] = day[v] + 1
            que.append(w)
if rest > 0:
    print(-1)
else:
    print(max(day))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 7)
 
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('{}-{}'.format(t, p))
        else:
            result.append('{}-{}'.format(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
        elif c in already_finish:
            match[i].pop(0)
        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 copy import deepcopy
N=int(input())

A=[[int(i) for i in input().split()] for _ in range(N)]
l=[0 for _ in range(N)]
ll=[0 for _ in range(N)]
r=[i for i in range(N)]
rr=[i for i in range(N)]
day=0
for _ in range(10**9):
    if min(l)==N-1:
        can=True
        break
    can=False
    for i in r:
        j=A[i][l[i]]-1
        if A[j][l[j]]-1==i:
            ll[i]+=1
            can=True
            if ll[i]==N-1:
              rr.remove(i)
    l=deepcopy(ll)
    r=deepcopy(rr)
    if can==False:
        break
    day+=1
if can==False:
    print(-1)
if can==True:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
 
class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)
 
        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)
 
        # print(hashmap)
 
        cnt = 0
        old_cnt = 0
        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in range(N):
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))
 
            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1
 
            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                
if __name__ == '__main__':
    Solution().main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    n = int(input())
    listA=[] #appendのために宣言が必要
    for i in range(n):
        listA.append(list(map(int,input().split())))
    
    daied = 0
    days = 0
    error = 0

    for i in range(100000000):
        shiai = [0]*n
        count = 0
        sumlen = 0
        """
        if days < i-1:
            error = 1
            break
        else:
        """
        for j in range(n-1):
            if 0 < len(listA[j]):
                a = listA[j][0]
                if 0 < len(listA[a-1]):
                    b = listA[a-1][0]-1
                    if( j == b and shiai[j] == 0 and shiai[a-1] == 0):
                        listA[j].pop(0)
                        listA[a-1].pop(0)
                        shiai[j] = 1
                        shiai[a-1] = 1
                        days = i
        
        for j in range(n):
            sumlen += len(listA[j])
            count += shiai[j]
        
        if count == 0 and sumlen > 0:
            error = 1
            break
        
        elif count == 0 and sumlen == 0:
            break

    if error == 0:
        print(days+1)
    else:
        print(-1)

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
items = []
from collections import deque

for i in range(N):
    items.append(deque(map(int, input().split())))

ans = 0
from collections import defaultdict

while True:
    used = set()
    flag = False
    for j in range(N):
        if j + 1 in used:
            continue
        if len(items[j]) >= 1:
            t = items[j][0]
            if t not in used and len(items[t - 1]) >= 1 and j + 1 == items[t - 1][0]:
                used.add(j + 1)
                used.add(t)
                items[j].popleft()
                items[t - 1].popleft()
                flag = True
    all_done = True
    for i in range(N):
        if len(items[i]) != 0:
            all_done = False
    if flag:
        ans += 1
    else:
        print(-1)
        exit()
    if all_done:
        break
    if ans >= 10 ** 4 // 2:
        print(N*(N-1)//2)
print(ans)

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)]
longest = 0
while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if depth[c] >= d:
		continue
	depth[c] = d
	if d > N*(N-1):
		break
	finish[c] = True
	e = None
	for e in edge[c]:
		x,y = min(c,e), max(c,e)
		candidate.append((e, d+1))
	if e == None:
		longest = max(longest, d)
all_finished = all(finish)
if all_finished:
	print(longest + 1)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[::-1]

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    for _ in range(10**9):
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]-1
            if  A[enemy][IDX[enemy]] == player+1:
                next_idx = i+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = i
        if flag:
            return -1
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
items = []
from collections import deque

for i in range(N):
    items.append(deque(map(int, input().split())))

ans = 0
from collections import defaultdict

while True:
    used = set()
    flag = False
    for j in range(N):
        if j + 1 in used:
            continue
        if len(items[j]) >= 1:
            t = items[j][0]
            if t not in used and len(items[t - 1]) >= 1 and j + 1 == items[t - 1][0]:
                used.add(j + 1)
                used.add(t)
                items[j].popleft()
                items[t - 1].popleft()
                flag = True
    all_done = True
    for i in range(N):
        if len(items[i]) != 0:
            all_done = False
    if flag:
        ans += 1
    else:
        print(-1)
        exit()
    if all_done:
        break
    if ans >= 10 ** 4:
        print(N*(N-1)//2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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)

#print(match)
today_match = set()
already_finish = set()
already_finish_count = 0
delete_index = {}
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)
            already_finish_count += 1
            match[i].pop(0)
            #print('pop', c, delete_index[c])
            match[delete_index[c]].pop(0)
            #print('match', match)
            could_make_match = True
        # 試合見つからなかった
        else:
            today_match.add(c)
            delete_index[c] = i
    if not could_make_match:
        result = -1
        break
    result += 1
    # print('day' + str(result))
    today_match = set()
    if already_finish_count == all_match_count:
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
k = 0
l = n * (n - 1) // 2
while(l):
    v = [(i, j) for i in range(n) for j in range(i)
         if a[i] and a[j] and a[i][-1] == j + 1 and a[j][-1] == i + 1]
    if not v:
        k = -1
        break
    for i, j in v:
        a[i].pop()
        a[j].pop()
    k += 1
    l -= len(v)
print(k)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N=int(input())

A=[[int(i) for i in input().split()] for _ in range(N)]
l=[0 for _ in range(N)]
ll=[0 for _ in range(N)]
r=[i for i in range(N)]
rr=[i for i in range(N)]
day=0
for _ in range(10**9):
    if min(l)==N-1:
        can=True
        break
    can=False
    for i in r:
        if l[i]==N-1:
            continue
        j=A[i][l[i]]-1
        if A[j][l[j]]-1==i:
            ll[i]+=1
            can=True
            if ll[i]==N-1:
              rr.remove(i)
    l=deepcopy(ll)
    r=deepcopy(rr)
    if can==False:
        break
    day+=1
if can==False:
    print(-1)
if can==True:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[::-1]

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    for _ in range(10**9):
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            #print(player, i, IDX[player])
            enemy = A[player][i]-1
            if  A[enemy][IDX[enemy]] == player+1:
                next_idx = i+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = i
        if flag:
            return -1
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()

def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []

    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if tmpl == l:
            print(-1)
            exit()
        tmpl = l[:]
        # print(l, ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ann = [[int(x) for x in input().split()]for i in range(n)]
# print(ann)

indexes = [0 for x in range(n+1)]
#
days = 0
match_count = 0
fight_persons = {}
while(match_count < (n*(n-1))//2):
    fight_persons = set([])
    # print(f"{days} day")
    # print(indexes)
    for self_i,an in enumerate(ann):
        self_i += 1
        # print(f"self_i = {self_i}")
        if self_i in fight_persons or n-1 <= indexes[self_i]:
            continue
        person_i = an[indexes[self_i]]
        # print(f"person_i = {person_i}")
        if person_i in fight_persons or n-1 <= indexes[person_i]:
            continue
        if ann[person_i-1][indexes[person_i]] == self_i:
            # print("fight!!!")
            # print(person_i,self_i)
            match_count += 1
            indexes[self_i] += 1
            indexes[person_i] += 1
            fight_persons.add(self_i)
            fight_persons.add(person_i)
    # print(fight_persons)
    if len(fight_persons) > 0:
        days += 1
    else:
        break


# print("+++++++++++++++")
if match_count < (n*(n-1))//2:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

Solution code:

# Setup
import sys
import collections
sys.setrecursionlimit(4100000)
a = int(input())
b = [collections.deque([int(i) for i in input().split()]) for _ in range(a)]
counter = 0
yesno = True
while len(b) != 0:
    found = False
    done = [False] * len(b)
    for i in range(len(b)):
        if len(b[i]) >= 1 and not done[i]:
            target = b[i][0]-1
            if not done[target] and len(b[target]) >= 1:
                if b[target][0] == i+1:
                    b[i].popleft()
                    b[target].popleft()
                    done[i] = True
                    done[target] = True
                    found = True
    if not found:
        break
    counter += 1
for a in b:
    if a != collections.deque([]):
        yesno = False
if not yesno:
    print(-1)
else:
    print(counter)

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]
longest = 0
while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if d > N*(N-1):
		break
	finish[c] = True
	e = None
	for e in edge[c]:
		x,y = min(c,e), max(c,e)
		dict_idx = x*M + y
		candidate.append((e, d+1))
	if e == None:
		longest = max(longest, d)
all_finished = all(finish)
if all_finished:
	print(longest + 1)
else:
	print(-1)

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

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

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

        for i in range(N-1):
            
            a = desired[i]
            if a < 0:
                continue
            b = desired[a-1]
            # a = A[i][0]
            # if a < 0:
            #     continue
            # b = A[a-1][0]
            # if b < 0:
            #     continue
            # matched
            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

                # 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

            


if __name__ == '__main__':
    main()

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
    cnt = 0
    while cnt < N * n // 2:
        used = [False] * N
        found = False
        for i in range(N):
            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
                    found = True
                    cnt += 1
        if not found:
            for i in range(N):
                if p[i] < n:
                    print(-1)
                    return
            break
        ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    #A = [ [ int(next(tokens)) - 1 for _ in range(N-1) ] for _ in range(N) ]  # type: "List[List[int]]"
    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
input = sys.stdin.readline


n = int(input())
li = [[int(x) for x in row.split()][::-1] for row in sys.stdin.readlines()]

cnt = 0
check = []
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in range(1,n):
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][-1]
        if temp <= i:
            continue
        if li[temp-1][-1] == i and temp not in check:
            del li[i-1][-1]
            del li[temp-1][-1]
            play += 1
            check.append(temp)
    cnt += 1
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

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

def make_match(match_list):
    output = []
    for pair in match_list:
        if match_list.count(pair) == 2:
            if pair not in output:
                output.append(pair)
    return output

counter = 0

for i in range((n * (n - 1))):
    match_list = []
    for index, lst in enumerate(a_list):
        if len(lst) == 0:
            continue
        if index + 1 < lst[0]:
            pair = (index + 1, lst[0])
        else:
            pair = (lst[0], index + 1)
        match_list.append(pair)
    match = make_match(match_list)
    if match == []:
        if a_list != [[]]*n:
            counter = -1
        break
    for pair in match:
        #print(match)
        a_list[pair[0] - 1].pop(0)
        a_list[pair[1] - 1].pop(0)
    counter += 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
k = 0
while(any(a)):
    v = [(i, j) for i in range(n) for j in range(i)
         if a[i] and a[j] and a[i][-1] == j + 1 and a[j][-1] == i + 1]
    if not v:
        k = -1
        break
    for i, j in v:
        a[i].pop()
        a[j].pop()
    k += 1
print(k)

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
    cnt = 0
    while cnt < N * n // 2:
        used = [False] * N
        found = False
        for i in range(N):
            if not used[i] and p[i] < n:
                j = A[i][p[i]]
                if not used[j] and p[j] < n and A[j][p[j]] == i:
                    used[i] = True
                    used[j] = True
                    p[i] += 1
                    p[j] += 1
                    found = True
                    cnt += 1
        if not found:
            for i in range(N):
                if p[i] < n:
                    print(-1)
                    return
            break
        ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ [ int(next(tokens)) - 1 for _ in range(N-1) ] for _ in range(N) ]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

N = int(input())

A = {}
for i in range(1, N+1):
    A[i] = list(map(int, input().split()))

count = 0
play = [0]
while play:
    play = []
    for i in A:
        if i in play:
            continue
        if not A[i]:
            continue
        j = A[i][0]
        if j in play:
            continue
        if not A[j]:
            continue
        if A[j][0] == i:
            play.append(i)
            play.append(j)
    if play:
        for i in play:
            del A[i][0]
        count += 1

for a in A:
    if A[a]:
        print(-1)
        sys.exit()

print(count)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver. 計算量はせいぜいO(n^2) < 10**6 程度だと想定したのだけれど、そうではないのか？それともほかの理由？
def judge_and_count(A_lst, already_played, played_count):
    count = 0
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

N = int(input())
n = N

data= [ [int(elm) - 1 for elm in input().split(" ")] for i in range(N)]
#print(data)

nexts = [0 for _ in range(n)]
goal = [N-1 for _ in range(n)]

day = 1
all_game = 0
end_game = n * (n-1) // 2
nows_tmp = [False for _ in range(n)]
while True:
    done = False
    #nows = []
    #nows = nows_tmp.copy()
    nows = [False for _ in range(n)]

    for jibun_i in range(n):
        next_i = nexts[jibun_i]
        #if next_i == n-1 or jibun_i in nows:
        if next_i == n-1 or nows[jibun_i]:
            continue

        #print(jibun_i, next_i)
        aite_i = data[jibun_i][next_i]

        #if data[aite_i][nexts[aite_i]] == jibun_i and aite_i not in nows:
        if data[aite_i][nexts[aite_i]] == jibun_i and not nows[aite_i]:
            done = True
            nexts[jibun_i] += 1
            nexts[aite_i] += 1
            #nows += [jibun_i, aite_i]
            nows[aite_i] = True
            nows[jibun_i] = True
            all_game += 1

    #if goal == nexts:
    if all_game == end_game:
        out = day
        break

    if not done:
        out = -1
        break
    
    day += 1

print(out)