Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
li = deque(list(map(int,input().split())) for i in range(1,n+1))

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][0]
        if temp <= i:
            continue
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(temp)
    cnt += 1
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 1:
                battle_dict[i].pop(0)
            else:
                battle_dict[i].pop(0)
                battle_dict.pop(i)
            if len(battle_dict[j]) > 1:
                battle_dict[j].pop(0)
            else:
                battle_dict[j].pop(0)
                battle_dict.pop(j)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        new = tuple(sorted([i, j[0]]))
        cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n = input()
mat = [map(int, raw_input().split()) for _ in xrange(n)]
d = 0

while True:
	d += 1
	#print '********** day', d
	ac = {}
	plist = []

	for i, row in enumerate(mat):
		if len(row) <= 0:
			continue
		a = row[0]

		k = tuple(sorted((i + 1, a)))
		if k not in ac:
			ac[k] = 1
		else:
			ac[k] += 1

	#print ac
	for k in ac:
		if ac[k] == 2:
			#print 'vs',k
			s,t = k
			plist.append(s-1)
			plist.append(t-1)

	for i in plist:
		mat[i].pop(0)

	left = sum(map(len, mat))
	# マッチなし、かつ残り試合があるなら矛盾
	if len(plist) == 0 and left > 0:
		d = -1
		break

	# 残試合なし？
	if left == 0:
		break

	#print 'result'
	#print mat

print d

Submission status: Time Limit Exceeded

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

days = 0
while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in [n for n in range(N-1) if fin[n]==False]:
        if matched[n]:
            continue
        op = An[n][deg[n]] - 1
        if An[op][deg[op]] == n + 1 and not matched[op]:
            flag = True
            matched[n] = True
            matched[op] = True
            deg[n] += 1
            deg[op] += 1
            if deg[n] == N - 1:
                fin[n] = True
            if deg[op] == N - 1:
                fin[op] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

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

    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = [list(map(int, input().split())) for _ in range(N)]

        already_p = set()
        days = 0
        done = set()
        while True:
            for i, a in enumerate(A):
                if len(a) == 0:
                    done.add(i + 1)
                    continue
                if i + 1 not in already_p and a[0] not in already_p and A[a[0] - 1][0] == i + 1:
                    already_p.add(i + 1)
                    already_p.add(a[0])
                    A[a[0] - 1] = A[a[0] - 1][1:]
                    A[i] = a[1:]

            if len(done) == N:
                break

            if len(already_p) == 0:
                print(-1)
                exit()

            already_p = set()
            days += 1

        print(days)


if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
i1=lambda x:int(x)-1
a=[list(map(i1,input().split())) for i in range(n)]
s=[0 for i in range(n)]
ans=0
f=0
l=n*(n-1)//2
c0=[0 for i in range(n)]
while f < l:
  c=list(c0)
  ans+=1
  nf=f
  for i in range(n-1):
    if c[i] == 0 and s[i] < n-1 :
      x=a[i][s[i]]
      if c[x] == 0 and a[x][s[x]] == i:
        c[i] = 1
        c[x] = 1
        s[x] += 1
        s[i] += 1
        f += 1
  if f == nf:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N=int(input())
    L=[[]]
    
    for i in range(N):
        a=list(map(int,input().split()))
        L.append(a)
    #print(L)
    Z=[0 for i in range(N+1)]
    day=0
    cnt=0
    for i in range(10**6+5):
        if cnt==N*(N-1)/2:
            break
        D=dict()
        CNT=0
        for j in range(1,N+1):
            if Z[j]==N-1 or j in D:
                continue
            elif L[L[j][Z[j]]][Z[L[j][Z[j]]]]==j and L[j][Z[j]] not in D:
                D[j]=1
                D[L[j][Z[j]]]=1
                X=L[j][Z[j]]
                Z[j]+=1
                Z[X]+=1
                CNT+=1
        if CNT==0:
            print(-1)
            exit()
        cnt+=CNT
        day+=1
    #print(L)
    #print(cnt)
    print(day)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 - 1):
    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)

Submission status: Time Limit Exceeded

Solution code:
*D, = open(0)
n = int(D[0])
data = []
for i in range(n):
    l = map(int, D[i+1].split())
    data.append([val-1 for val in l])
    
    
from collections import deque
table = []
for i in range(n):
    table.append(deque())
    for j in data[i]:
        if i > j:
            table[i].append('{},{}'.format(j,i))
        else:
            table[i].append('{},{}'.format(i,j))
        
        
cnt = 0
while True:
    candi = {}
    END = True
    del_idx = []
    for i, que in enumerate(table):
        if que:
            if que[0] in candi:
                del_idx.append([candi[que[0]],i])
            else:
                candi[que[0]] = i

    END = True
    for it in del_idx:
        table[it[0]].popleft()
        table[it[1]].popleft()
        END = False
    if END:
#         print('end')
        break
    cnt += 1
    
INVALID = True
for it in table:
    if not it:
        INVALID = False
        break

if INVALID:
    print('-1')
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[0 for i in range(N+1)]]
for i in range(1,N+1):
    A.append([int(x) for x in input().split()] + [0])

date = 0
match = 0
OK = True
while match < N*(N-1)//2:
    temp = set()
    for i in range(1,N):
        j = A[i][0]
        if A[j][0] == i:
            if j > i:
                temp.add(i)
                temp.add(j)
                match += 1
    if temp == set():
        OK = False
        break
    for i in temp:
        A[i].pop(0)
    date += 1

if OK:  print(date)
else: print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from collections import deque

def main():
	n = int(input().strip())
	dqlist = [0] * (n+1)
	for i in range(n):
		v = list(map(int, input().strip().split()))
		dqlist[i+1] = deque(v)
	day = 0
	zeroc = 0
	for _ in range(1000000):
		picked = [0] * (n+1)
		changed = False
		for i in range(1, n+1):
			if picked[i] == 1:
				continue
			if len(dqlist[i]) == 0:
				continue
			if dqlist[dqlist[i][0]][0] == i:
				if picked[dqlist[i][0]] == 1:
					continue
				# OK
				changed = True
				c = dqlist[i].popleft()
				dqlist[c].popleft()
				picked[i] = 1
				picked[c] = 1
				if len(dqlist[i]) == 0:
					zeroc += 1
				if len(dqlist[c]) == 0:
					zeroc += 1
		if changed == False:
			if zeroc == n:
				print(day)
				return
			else:
				print(-1)
				return
		day += 1

if __name__ == '__main__':
	main()

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:
import sys

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

A.insert(0,[])

day = 0
pop_set = set()

while True:
  day += 1
  empty_judge = True
  pop_set.clear()
  
  for i in range (1,N):
    if A[i]:
      vs = A[i][0]
      if A[vs][0] == i:
        pop_set.add(i)
        pop_set.add(vs)
  if pop_set == set():
    print(-1)
    sys.exit()
  for j in range(len(pop_set)):
    A[list(pop_set)[j]].pop(0)
    
  for k in range(N):
    if A[k]:
      break
    if k == N-1:
      print(day)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
nm2 = n - 2
nm1 = n - 1
maxga = n
maxgan = n

d = 0
for ii in range(n*n*2):
    maxga = maxgan
    F = [0] * n
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= nm2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            sai = S[aite]
            if sai <= nm2 and A[aite][sai] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
                if sai == nm2:
                    maxgan -= 1
                if si == nm2:
                    maxgan -= 1

        i = (i+1) % n
        co += 1
        #print(S,maxga//2)
        if co == nm1 or ga == maxga//2:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)

first = a_list[:, 0]
target = n_index[first[first] == n_index]
a_index[target] += 1
ans = 1
for i in range(N * (N-1) // 2):

    cand = a_list[target, a_index[target]]
    target_index = (a_list[cand, a_index[cand]] == target)
    target = np.unique(np.hstack((cand[target_index], target[target_index])))
    if len(target) == 0:
        break

    a_index[target] += 1
    ans += 1

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
A=collections.defaultdict(list)
living=set()
for i in range(1,N+1):
    aij=list(map(int,input().split()))
    A[i] = aij
    living.add(i)

uses = [0] * (N+1)

donotchange=False
day=0
while True:
    day_change=False
    used = [False] * (N+1)


    for i in living:
        if used[i] == False and uses[i] < N-1:
            target = A[i][uses[i]]
            target_top = A[target][uses[target]]

            if target_top == i and used[target]==False:
                used[i] = True
                used[target] = True
                uses[i]+=1
                uses[target]+=1
                day_change=True
            else:
                pass
    
    day+=1

    if day_change==False:
        donotchange=True
        break

    isend=True
    for i in range(1,N+1):
        if uses[i] < N-1:
            isend=False

        if i in living and uses[i] >= N-1:
            living.remove(i)


    if isend==True:
        break

if donotchange==True:
    print('-1')
else:
    print(day)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= deque( [ int(x)-1 for x in sys.stdin.readline().split() ] )
#
tot= (n*(n-1))//2
now= 0
c= 0
for _ in range(tot):
    lst= []
    for i in range(n):
        ai = a[i]
        if not ai: continue
        j  = ai[0]
        if j<i: continue
        aj = a[j]
        if aj[0]==i:
            lst.append(i)
            now+= 1
    #
    for i in lst:
        a[ a[i].popleft() ].popleft()
    #
    c+= 1
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

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

def check_finish():
    for i in range(n):
        if len(a[i]) > 0:
            return False
    return True

def match():
    h = [i for i in range(n)]
    #print(h)
    c = 0
    while len(h) > 0:
        i = h.pop(0)
        if len(a[i]) == 0:
            continue
        aite = a[i][0]-1
        #print(i,aite)
        if a[aite][0] == i+1 and aite in h:
            c = c + 1
            h.remove(aite)
            a[i].pop(0)
            a[aite].pop(0)
    return c       
d = 0            
while not check_finish():
    d += 1
    c = match()
    if c == 0:
        d = -1
print(d)

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    op = [[]]
    for i in range(N):
        op.append(deque(list(map(int, input().split()))))

    day = 0
    count = (N * (N - 1)) // 2
    can = 1
    while True:
        if count == 0:
            break
        if can == 0:
            day = -1
            break
        played = [0] * (N + 1)
        k = 1
        k_seen = 1
        end_day = 0
        can = 0
        while True:
            if len(op[k]) > 0:
                opponent = op[k][0]
                if len(op[opponent]) > 0:
                    if op[opponent][0] == k:
                        if played[k] == 0 and played[opponent] == 0:
                            count -= 1
                            can = 1
                            op[k].popleft()
                            op[opponent].popleft()
                        played[k] = 1
                        played[opponent] = 1
                        k_seen += 1
                        k = k_seen
                        while played[k] == 1:
                            k += 1
                            if k == N + 1:
                                day += 1
                                end_day = 1
                                break
                    else:
                        played[k] = 1
                        if played[opponent] == 0:
                            k = opponent
                        else:
                            k_seen += 1
                            k = k_seen
                            while played[k] == 1:
                                k += 1
                                if k == N + 1:
                                    day += 1
                                    end_day = 1
                                    break
            else:
                played[k] = 1
                k_seen += 1
                k = k_seen
                while played[k] == 1:
                    k += 1
                    if k == N + 1:
                        day += 1
                        end_day = 1
                        break
            if end_day == 1:
                break

    print(day)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))
# print(a)
b = [[0, 0] for _ in range(n)]
# print(b)
cnt = 0
cntmax = n*(n-1)
while cnt < cntmax:
	flag = True
	for i in range(n):
		pass1 = b[i][0]       
		if pass1 >= n-1: continue
		pass2 = b[a[i][pass1] - 1 ][0]      
		if pass2 >= n-1: continue
		
		if a[a[i][pass1] - 1][pass2] - 1 == i:
			b[a[i][pass1] - 1][1] = b[i][1] = max(b[i][1], b[a[i][pass1] - 1][1]) + 1
			b[a[i][pass1] - 1][0] += 1
			b[i][0] += 1
			cnt += 2
			flag = False
			# print("done");print(a);print(b)
	if flag:
		print(-1)
		exit()
	# print(a)
	# print(b)
ans = 0
for i in range(n):
	ans = max(ans, b[i][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 1:
                battle_dict[i].pop(0)
            else:
                battle_dict[i].pop(0)
                battle_dict.pop(i)
            if len(battle_dict[j]) > 1:
                battle_dict[j].pop(0)
            else:
                battle_dict[j].pop(0)
                battle_dict.pop(j)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(sys.stdin.readline())
a_dict = {}
for i in range(N):
  a_dict[i] = [int(a) -1 for a in sys.stdin.readline().split()]

ans = 0
while len(a_dict) > 0:
  flag = False
  entried = []
  for i  in range(N):
    if i in entried or len(entried) == N:continue
    if i in a_dict:
      i2 = a_dict[i][0]
      if a_dict[i2][0] == i and i2 not in entried:
        entried.extend([i,i2])
        del a_dict[i2][0], a_dict[i][0]
        if len(a_dict[i]) == 0: del a_dict[i]
        if len(a_dict[i2]) == 0: del a_dict[i2]
        flag = True
  if flag is False:break
  ans += 1
print(ans if len(a_dict) == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
nt = []
for i in range(n):
  tmp = list(map(int, input().split()))
  nt.append(tmp)

day = 0
j = np.zeros(n,dtype = int)
  
while(True):
  #print(j)
  tmp = []
  for i in range(n):
    if j[i] < n-1 and nt[nt[i][j[i]]-1][j[nt[i][ j[i] ]-1]] == i+1:
      tmp.append(i)
  #print(tmp)
  if len(tmp) == 0:
    break
  for i in tmp:
    j[i] += 1
  day += 1
  
error = 0
for i in range(n):
  if j[i] != n-1:
    day = -1
    break

print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
league = []
match = {}
ll = []
for i in range(n):
    league.append(list(map(int, input().split())))
    match[i+1] = league[i][-1]
    ll.append(n-3)
ans = 0
cnt = 0
tmp = [0]
while cnt < n and tmp:
    tmp = []
    for k,v in match.items():
        if v in match and match[v] == k:
            tmp.append(v)
    for i in tmp:
        if ll[i-1] < 0:
            cnt += 1
            match[i] = 0
        else:
            match[i] = league[i-1][ll[i-1]]
            ll[i-1] -= 1
    ans += 1
print(ans if n == cnt else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
al = [[] for _ in range(n+1)]
for i in range(n):
    a = list(map(int, input().split()))
    al[i+1] = [-1]+a
idx = [1 for _ in range(n+1)]
idx[0] = n
res = 0
while True:
    res += 1
    s = set()
    for i in range(1,n+1):
        used = [False for _ in range(n+1)]
        used[i] = True
        t = i
        if idx[t]>=n:
            continue
        u = al[t][idx[t]]
        if idx[u]>=n:
            continue
        v = al[u][idx[u]]
        while t!=v:
            t = u
            if used[t]:
                print(-1)
                exit()
            used[t] = True
            if idx[t]>=n:
                break
            u = al[t][idx[t]]
            if idx[u]>=n:
                break
            v = al[u][idx[u]]
        s.add(t)
        s.add(u)
    for i in s:
        idx[i] += 1
    flag = True
    for i in idx:
        if i<n:
            flag = False
            break
    if flag:
        break
print(res)

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
while True:
    done = False
    nows = []
    for jibun_i in range(n):
        next_i = nexts[jibun_i]
        if next_i == n-1:
            continue

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

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

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

print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
player = []
for i in range(n):
    line = [int(x)-1 for x in input().split()]
    player.append(line)
    
done = [0 for _ in range(n)]

def check_finish():
    for d in done:
        if d != (n-1):
            return False
    return True
  
count = 0
ok_flg = False

while True:
    if check_finish():
        ok_flg = True
        break
    play_list = []
    for i in range(n):
        if (not i in play_list) and (not done[i] == (n-1)):
            p1 = i
            p2 = player[p1][done[i]]
            if not p2 in play_list:
                if p1 == player[p2][done[p2]]:
                    done[p1] += 1
                    done[p2] += 1
                    play_list.append(p1)
                    play_list.append(p2)
                
    if play_list == []:
        break
        
    count += 1

if ok_flg:
    print(count)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)