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())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])
 
ans = 0
allpc = 0
while (True):
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i].popleft()
      if aite not in tmpset:
        aiteaite = dic[aite].popleft()
        if aiteaite == i:
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
          allpc += 1
        else:
          dic[i].appendleft(aite)
          dic[aite].appendleft(aiteaite)
      else:
        dic[i].appendleft(aite)
 
  if playcount > 0:
    ans += 1
  else:
    break
 
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

a = int(input())
b = [[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].pop(0)
                    b[target].pop(0)
                    done[i] = True
                    done[target] = True
                    found = True
    if not found:
        break
    counter += 1
for a in b:
    if a != []:
        yesno = False
if not yesno:
    print(-1)
else:
    print(counter)

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

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
new_search_index=list(range(1,N+1))
for answer in range(1,N**3):
  matched_flag=[False]*(N+1)

  search_index=new_search_index;
  new_search_index=[]
  #print(search_index)
  for i in search_index:
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      new_search_index.append(i)
      new_search_index.append(ai_next)
  
  if len(new_search_index)==0:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import sys, math; from collections import deque; readline=sys.stdin.readline;

N = int(readline())
A = [deque(map((lambda x:int(x) - 1), readline().split())) for n in range(N)]


count = 0
while True:
    locked = [False for n in range(N)]
    pop_count = 0
    for n in range(N):
        if locked[n]:
            continue
        if len(A[n]) == 0:
            continue
        a = n
        locked[n] = True
        while True:
            b = A[a][0]
            if locked[b]:
                break
            locked[b] = True
            if a == A[b][0]:
                A[a].popleft()
                A[b].popleft()
                pop_count += 1
                break
            a = b
        
    if pop_count == 0:
        break
    else:
        count += 1

if any(len(q) != 0 for q in A):
    print(-1)
else:
    print(count)

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:
                table[candi[que[0]]].popleft()
                table[i].popleft()
                END = False
            else:
                candi[que[0]] = i

    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:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

def main():
    A_list = []
    if 'LOCAL' in os.environ:
        N = 1000
        for i in range(N):
            tmp = [j for j in range(N) if i != j]
            random.shuffle(tmp)
            A_list.append(tmp)

    else:
        N = _I()
        A_list = [LI() for i in range(N)]
        #  for i in range(N):
        #      A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx in range(N):
        new_A_list[aidx] = tuple(i-1 for i in A_list[aidx])
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = {i:0 for i in range(N)}
    done_player_list = {}
    position_sum = 0
    done_sum = (N-1)*N
    #  all_done_players = set()
    N_1 = N - 1
    for _ in range(10**7):
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

        for i in range(N_1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if done_player_list.get(i):
                continue

            #  if i in all_done_players:
            if current_position_list.get(i) == N_1:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list.get(i)[current_position_list.get(i)]
            if opponent_idx < i:
                continue
            if done_player_list.get(opponent_idx):
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list.get(opponent_idx)[current_position_list.get(opponent_idx)] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                #  done_player_list += (opponent_idx, i)
                #  done_player_list[i] = True
                #  done_player_list.add(opponent_idx)
                done_player_list[opponent_idx] = True
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                #  if current_position_list[i] == N-1:
                #      all_done_players.add(i)
                #  if current_position_list[opponent_idx] == N-1:
                #      all_done_players.add(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

        if not is_ok:
            # 1試合も成立しなかったらストップする
            print(-1)
            exit()

        done_player_list = {}
        current_day += 1

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

Submission status: Time Limit Exceeded

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

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)

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
while True:
    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, time
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
#print(*a, sep="\n")
opponent = [-1 for _ in range(n)]
played = list(range(n))
match = 0
day = 0
while match < n*(n-1)//2:
	approved = False
	for i in played:
		if a[i] != []:
			opponent[i] = a[i].pop()-1
	played = []
	#print(opponent)
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			played += [i, opponent[i]]
			opponent[opponent[i]] = -1
			opponent[i] = -1
	#print(opponent)
	if not approved:
		print(-1)
		sys.exit()
	day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

def main():
    A_list = []
    if 'LOCAL' in os.environ:
        N = 1000
        for i in range(N):
            tmp = [j for j in range(N) if i != j]
            random.shuffle(tmp)
            A_list.append(tmp)

    else:
        N = _I()
        A_list = [LI() for i in range(N)]
        #  for i in range(N):
        #      A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx in range(N):
        new_A_list[aidx] = tuple(i-1 for i in A_list[aidx])
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = {i:0 for i in range(N)}
    done_player_list = {}
    position_sum = 0
    done_sum = (N-1)*N
    #  all_done_players = set()
    N_1 = N - 1
    for _ in range(10**7):
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

        for i in range(N_1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if done_player_list.get(i):
                continue

            #  if i in all_done_players:
            if current_position_list.get(i) == N_1:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list.get(i)[current_position_list.get(i)]
            if done_player_list.get(opponent_idx):
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list.get(opponent_idx)[current_position_list.get(opponent_idx)] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                #  done_player_list += (opponent_idx, i)
                done_player_list[i] = True
                #  done_player_list.add(opponent_idx)
                done_player_list[opponent_idx] = True
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                #  if current_position_list[i] == N-1:
                #      all_done_players.add(i)
                #  if current_position_list[opponent_idx] == N-1:
                #      all_done_players.add(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

        if not is_ok:
            # 1試合も成立しなかったらストップする
            print(-1)
            exit()

        done_player_list = {}
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
import time
s_time = time.time()


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

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
print(cnt)

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

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

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

print(out)

Submission status: Time Limit Exceeded

Solution code:

def judge_and_count(A_lst, already_played, played_count, more_play, nexts):
    count = 0
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if more_play[i] and already_played[i] == 0:
                p1 = i
                p2 = A_lst[p1][nexts[p1]]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                
                if A_lst[p2][nexts[p2]] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    nexts[p1] += 1
                    nexts[p2] += 1
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if len(A_lst[p1]) == 0:
                        more_play[p1] = False
                    if len(A_lst[p2]) == 0:
                        more_play[p2] = False

        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)
more_play = [True]*(N+1)
nexts = [0]*(N+1)

A_lst = [[]]


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


ans = judge_and_count(A_lst, already_played, played_count, more_play, nexts)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
new_search_index=list(range(1,N+1))
for answer in range(1,N**3):
  matched_flag=[False]*(N+1)
  unchanged=True

  search_index=new_search_index;
  new_search_index=[]
  for i in search_index:
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
      new_search_index.append(i)
      new_search_index.append(ai_next)
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.8:
            print((N*(N-1))//2)
            break
        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:
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 len(an) <= indexes[self_i]:
            continue
        person_i = an[indexes[self_i]]
        # print(f"person_i = {person_i}")
        if person_i in fight_persons or len(ann[person_i-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:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
r = set(list(range(n)))
while True:
    if not r:
        print(ans)
        break
    tmp = 0
    for j in r:
        if not a[j]:
            tmp += 1
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
    for j in range(n):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    r.remove(j)
    if flag:
        print(-1)
        break
    else:
        ans += 1

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
def bat(i,j):
  return 10000*min([i,j])+max([i,j])
e_list=[]
for i in range(N):
  ls=[int(e) for e in input().split()]
  for j in range(N-2):
    e_list.append([bat(i+1,ls[j]),bat(i+1,ls[j+1])])
L=[]
node=[]
for i in range(N):
  for j in range(i+1,N):
    node.append(10000*(i+1)+j+1)
S=[]
suka=[e[1] for e in e_list]
snode=set(node)
ssuka=set(suka)
S=list(snode-ssuka)
count=0
while S!=[]:
  SS=[]
  count+=1
  while S!=[]:
    x=S[0]
    S.pop(0)
    ls=[e for e in e_list if e[0]==x]
    for s in ls:
      e_list.remove(s)
      ls2=[e for e in e_list if e[1]==s[1]]
      if len(ls2)==0:
        SS.append(s[1])
  S=SS    
if len(e_list)>0:
  print(-1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [[int(x)-1 for x in input().split()] for _ in range(N)]
cnt = 0
g = [-1] * N
while(1):
    need_break = 1
    loop = 1
    for u, to_lst in enumerate(A_list):
        if (g[u] != -1 or len(to_lst) == 0): continue
        g[u] = to_lst.pop(0)
    for i, to in enumerate(g):
        need_break *= (to == -1)
        if (to != -1 and i == g[to]):
            g[i] = -1
            g[to] = -1
            loop = 0
    if (need_break):
        break
    if (loop):
        print(-1)
        exit()
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n**2 //2)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count, more_play, nexts):
    count = 0
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if more_play[i] and already_played[i] == 0:
                p1 = i
                p2 = A_lst[p1][nexts[p1]]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                
                if A_lst[p2][nexts[p2]] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    nexts[p1] += 1
                    nexts[p2] += 1
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if len(A_lst[p1]) == 0:
                        more_play[p1] = False
                    if len(A_lst[p2]) == 0:
                        more_play[p2] = False

        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)
more_play = [True]*(N+1)
nexts = [0]*(N+1)

A_lst = [[]]


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


ans = judge_and_count(A_lst, already_played, played_count, more_play, nexts)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC139E - League
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = deque(A[x : x + N - 1])
    ans, flg, matched = 0, 0, set()
    while B:
        for i in list(B.keys()):
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    flg = 1
                    if not B[i]:
                        del B[i]
                    if not B[x]:
                        del B[x]
        if flg:
            ans += 1
            flg, matched = 0, set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
A = []
 
for _ in range(N):
	A.append(list(map(int, input().split())))
	
 
	
played_flg = 1
day = 0
played_game = 0
need_game = N * (N - 1) / 2
 
while played_flg:
	played_flg = 0
	day += 1
	game_played = [False for _ in range(N)]
	for i in range(N):
		# print(game_played)
		if len(A[i]) != 0 and A[A[i][0] - 1][0] - 1 == i: 
			if game_played[A[i][0] - 1] == False:
				if game_played[i] == False:
					# print(i, A[i][0] - 1)
					game_played[A[i][0] - 1], game_played[i] = True, True
					played_flg = 1
					played_game += 1
					A[A[i][0] - 1].pop(0)
					A[i].pop(0)
	if played_game == need_game:
		break
 
if played_flg == 0:
	print(-1)
else:
	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
            del match[i]
        else:
            match[i] = league[i-1][ll[i-1]]
            ll[i-1] -= 1
    ans += 1
print(ans if n == cnt else -1)