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:
def main():    
    n = int(input())
    a = [list(reversed(list(map(int,input().split())))) for _ in range(n)]
    ans = 0
    c = 0
    nn = n*(n-1)//2
    while True:
        pop_list = []
        pap = pop_list.append
        for i in range(n):
            for j in range(i+1,n):
                if a[i] and a[j]:
                    if a[i][-1]-1 == j and a[j][-1]-1 == i:
                        pap(i)
                        pap(j)
                        break
        if not pop_list:
            ans = -1
            break
        for i in pop_list:
            _ = a[i].pop(-1)
        c += len(pop_list)//2
        ans += 1
        if c == nn:
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#
import random


def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0
    targets = list(range(n))
    random.shuffle(targets)

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC139e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

day = 0
#print(a)
while (True):
    l = set()
    for i in range(n):
        if (len(a[i])!=0 and len(a[a[i][0] - 1])!=0 and a[a[i][0] - 1][0]-1 == i):
            l.add(i)
    if (len(l) == 0):
        break
    for i in l:
        a[i].pop(0)
    #print(l)
    l.clear()
    day += 1
    #print(a)
count=0
for i in range(n):
    count += len(a[i])
if(count==0):
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a[:])
count = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  for k in dic.keys():
    k = int(k)
    if dic[k]==deque([]):
      nokori += 1
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if dic[p2]==deque([]):
      print(-1)
      break
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

Submission status: Time Limit Exceeded

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

td = []
ans = 0
skip = 0
execflg = False
while 1:
        for idx, val in enumerate(A):
                if not val:
                        skip += 1
                        continue
                oppidx = val[0] - 1
                opp = A[val[0] - 1][0]
                if idx in td or oppidx in td:
                        continue
                
                if opp == idx + 1:
                        execflg = True
                        A[idx].pop(0)
                        A[oppidx].pop(0)
                        td.append(idx)
                        td.append(oppidx)
        else:
                if execflg:
                        td.clear()
                        ans += 1
                        execflg = False
                        skip = 0
                else:
                        if skip == N:
                                print(ans)
                        else:
                                print(-1)
                        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys


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

    loc = [n-2] * n

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import copy
n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
new_ls = []
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i+1] = inp
    new_ls.append(tuple(sorted([i+1, inp[0]])))
cur_stage.update(new_ls)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    for _ in range(N):
        A.append(list(map(int,input().split())))
    # next_pos = [A[i].pop(0) for i in range(N)]
    next_pos = []
    for i in range(N):
        next_pos.append(A[i].pop(0))
    ans = 0
    check = [0 for _ in range(N)]
    while True:
        end = True
        already = set()
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already or i in already:
                continue
            if i == next_pos[now] - 1:
                if end:
                    end = False
                if A[i]:
                    next_pos[i] = A[i].pop(0)
                else:
                    next_pos[i] = 0
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = 0
                already.add(i)
                already.add(now)
        ans += 1
        if end:
            ans = -1
            break
        if next_pos == check:
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

import time

st = time.time()

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# グラフつくる
nodes = set()
graph = defaultdict(list)
ins = defaultdict(int)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

        nodes.add(a * N + b)
        nodes.add(c * N + d)

# トポロジカルソート
S = []
for v in nodes:
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != len(nodes):
    print(-1)
    exit()

seen = []


@lru_cache(maxsize=None)
def dfs(v):
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())) + [-1])
day = 0
match = [0 for i in range(n)]
while match != [n - 1 for i in range(n)]:
    add = [False for i in range(n)]
    for i in range(n):
        j = a[i][match[i]] - 1
        if a[j][match[j]] - 1 == i:
            add[i] = True
            add[j] = True
    if add != [False for i in range(n)]:
        match = [match[i] + int(add[i]) for i in range(n)]
        day += 1
    else:
        break
else:
    print(day)
    sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:

def main():
    
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < N + 1000:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1]: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

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

AA = [list(map(int, input().split())) for _ in range(N)]

next_play = []
today_plan = [0] * N
for a in AA:
    next_play.append(a[0])


ans = 0
while True:
    for i in range(N):
        if today_plan[i] == -1:
            continue
        aite = next_play[i]
        if next_play[next_play[i] - 1] == -1:
            continue

        if (i+1) == next_play[next_play[i]-1] and today_plan[aite-1] != -1:
            today_plan[i], today_plan[next_play[i]-1] = -1, -1
            AA[i].pop(0)
            AA[next_play[i] - 1].pop(0)

            if len(AA[i]) != 0:
                next_play[i] = AA[i][0]
            else:
                next_play[i] = -1
            if len(AA[aite - 1]) != 0:
                next_play[aite - 1] = AA[aite - 1][0]
            else:
                next_play[aite - 1] = -1

    if sum(today_plan) == 0:
        print(-1)
        exit()
    else:
        today_plan = [0] * N
    ans += 1
    if next_play == [-1] * N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy
# Your code here!
n=int(input().rstrip())
a=[]
#been=[]
cnt=[]
for i in range(n):
    cnt.append(0)
   # been.append(0)
    a.append(input().rstrip().split(" "))
    for j in range(n-1):
        a[i][j]=int(a[i][j])
ans=0
day=0
last=int(n*(n-1)/2)


while(not last==0):
    olast=last
    day=day+1
    for i in range(n):
        cnt[i]=0
     #   been[i]=0
    for i in range(n):
        if(cnt[i]==1 or len(a[i])==0):# or been[i]==1):
            continue
        else:
            s=a[i][0]
            if(len(a[s-1])==0 or cnt[s-1]==1 or i >s-1):
                continue
            #been[i]=1
            if( i+1==a[s-1][0] and s==a[i][0]  ):
                cnt[i]=1
                cnt[s-1]=1
                last=last-1
                del a[i][0]
                del a[s-1][0]
    #print(a)
    #print(last)
    if(last==olast):
        day=-1
        break
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys

  sys.setrecursionlimit(10**7)
  readline = sys.stdin.readline

  
  n = int(readline())
  a = [list(map(int,readline().split())) for _ in range(n)]
  c = [0]*n
  d = 0
  m = list(range(n))
  
  while m:
    candidate = []
    for i in m:
      if i in candidate:
        continue
      j = a[i][c[i]]-1
      if a[j][c[j]]-1 == i:
        candidate += [i]
        candidate += [j]
    if candidate:
      for i in candidate:
        c[i]+=1
        if c[i] == n-1:
          m.remove(i)
      d+=1
    else:
      print(-1)
      quit()
      
  print(d)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = [int(j) - 1 for j in input().split()]
    A[i] += reversed(a)

empty = [[] for i in range(N)]
ans = 0
while(True):
    flag = False
    game_flag = [False] * N
    for i in range(N):
        if game_flag[i] == False and A[i] != []:
            j = A[i][-1]
            if game_flag[j] == False and A[j] != [] and A[j][-1] == i:
                flag = True
                game_flag[i] = True
                game_flag[j] = True
                A[i].pop()
                A[j].pop()
    ans += 1
    if A == empty:
        break
    elif flag == False:
        ans = -1
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [[int(i) for i in input().split()] for j in range(n)]
c = 0
gamesNum = 0
empty = False

while not empty:
  flag = [1] * n
  for i in range(n):
    if flag[i] and len(a[i]):
      opponent = a[i][0] - 1
      if flag[opponent] and len(a[opponent]) and a[opponent][0] - 1 == i:
        flag[i] = 0
        flag[opponent] = 0
        gamesNum += 1
        a[i].pop(0)
        a[opponent].pop(0)

  if gamesNum:
    c += 1
    gamesNum = 0
  else:
    c = -1    
    break

  for i in range(n):
    if len(a[i]):
      break
    if i == n-1:
      empty = True

print(c)

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

def f(N, A):
    ps = [0]*N
    numOfDays = 0
    
    while True:
        Q = set()
        numOfPlays = 0

        for p1 in range(1, N+1):
            if p1 in Q or ps[p1-1] >= N-1:
                continue

            p2 = A[p1-1][ps[p1-1]]

            if p2 in Q or ps[p2-1] >= N-1:
                continue

            p3 = A[p2-1][ps[p2-1]]

            if p1 == p3:
                ps[p1-1] += 1
                ps[p2-1] += 1
                numOfPlays += 1

                Q.add(p1)
                Q.add(p2)

        if numOfPlays == 0:
            for i in range(N):
                if ps[i] < N-1:
                    return -1
                    
            return numOfDays

        numOfDays += 1


    



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

    print(f(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

import sys
input = sys.stdin.readline


n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
                    if num >= n * (n - 1) // 2:
                        print(day)
                        exit()
    if (len(visit) == 0):
        print(-1)
        exit()
    if num >= n * (n - 1) // 2:
        print(day)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

import time

st = time.time()

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# グラフつくる
nodes = set()
graph = defaultdict(list)
ins = defaultdict(int)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

        nodes.add(a * N + b)
        nodes.add(c * N + d)

# トポロジカルソート
S = []
for v in nodes:
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != len(nodes):
    print(-1)
    exit()

seen = []


@lru_cache(maxsize=None)
def dfs(v):
    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=deque([deque([int(_)-1 for _ in input().split()]) for __ in range(n)])
f=[0 for _ in range(n)]
ff=0
m=n*(n-1)//2
d=0
while True:
    for i in range(n):
        if f[i]==0:
            if a[i] != deque([]):
                k=a[i][0]
                if f[k]==0:
                    if a[k][0]==i:
                        f[i]=1
                        f[k]=1
                        m-=1
                        a[k].popleft()
                        a[i].popleft()
                        ff=1
    if ff:
        f=[0 for _ in range(n)]
        d+=1
        ff=0
        if m==0:
            print(d)
            break
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

game = [0]

for _ in range(n):
    comp = list(map(int, input().split()))
    game.append(comp[::-1])

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == []:
            continue

        you = game[me][-1]
        if you in finish or game[you] == []:
            continue
        else:
            if game[you][-1] == me:
                finish.add(game[you].pop())
                finish.add(game[me].pop())
                possible = True
                count += 1
            else:
                continue

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

    if count == final:
        print(day)
        exit()

Submission status: Time Limit Exceeded

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

day = 0
judge = 1
while judge != 0:
	list = []
	for i in range(N):
		if len(a[i]) > 0:
			if a[a[i][0]-1][0] == i+1:
				list.append(i)
	for i in list:
		a[i].pop(0)
	day += 1
	#print(list)
	if len(list) == 0:
		judge = 0
		for i in range(N):
			if len(a[i]) != 0:
				judge = 1
		if judge == 1:
			print(-1)
			exit()
	
print(day-1)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        a = list(map(int, input().split()))
        q = collections.deque()
        for i in a:
            q.append(i)
        Q.append(q)
        
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            for j in range(i+1, len(Q)):
                if len(Q[j]) == 0 or gamed[j] != 0:
                    continue
                if Q[i][0] == j+1 and Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    gamed[i] = 1
                    gamed[j] = 1
                    break
        days += 1
        if not b:
            print(-1)
            return
        if all(len(q) == 0 for q in Q):
            break

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) + [0] for _ in range(N)]
Ai = [0] * N

ans, match, nmatch = 0, 0, N * (N - 1) // 2
while match < nmatch:
    ans, pair = ans + 1, []
    for i in range(N):
        if A[A[i][Ai[i]] - 1][Ai[A[i][Ai[i]] - 1]] == i + 1 and not {i + 1, A[i][Ai[i]]} in pair:
            pair.append({i + 1, A[i][Ai[i]]})
            match += 1
    for p in pair:
        for pi in p:
            Ai[pi - 1] += 1
    if len(pair) == 0:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0

cc = 0

ccc = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです
m = (N*(N-1))//2
n = 100000
for i in range(min(m,n)):#周回
  btlf = [False for i in range(N)]#リセット
  ccc = 0
  for j in range(N):
    #print(idx)
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if a>j:
        if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
          idx[a-1]+=1
          btlf[a-1] = True
          idx[j]+=1
          btlf[j] = True
          cc+=1
          ccc+=1
  if cc == m:#idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if ccc == 0:#対戦が一度もなければ打ち切ります
    break
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [ inpl() for _ in range(N) ]
nextgame = [0] * N
waitlist = []
player = 1
day = 0
totalgames = N*(N-1)//2
donegames = 0
while donegames < totalgames:
    day += 1
    readyflag = [True]*N
    todaygames = 0
    for player in range(1,N+1):
        if not readyflag[player-1] or nextgame[player-1] >= N-1:
            continue
        opp = A[player-1][nextgame[player-1]]
        if not readyflag[opp-1]:
            continue
        opp_opp = A[opp-1][nextgame[opp-1]]
        if opp_opp == player:
            nextgame[player-1] += 1
            nextgame[opp-1] += 1
            readyflag[player-1] = False
            readyflag[opp-1] = False
            todaygames += 1

    if todaygames == 0:
        print(-1)
        break
    else:
        donegames += todaygames
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  l=[]
  for _ in range(n):
    _l=LI()
    _l.reverse()
    l.append(_l)

  c=n*(n-1)
  ans=1
  nagasa=[n-1]*n
  while True:
    m=[0]*n
    _c=c

    for i in range(n):
      if c<=0:
        return ans

      if m[i]!=0:
        continue

      if nagasa[i]!=0:
        a=l[i][-1]-1

        if a<i:
          continue

        if m[a]!=0:
          continue

        if nagasa[a]!=0:
          if l[a][-1]==i+1:
            l[a].pop()
            l[i].pop()
            m[a]=1
            m[i]=1
            nagasa[a]-=1
            nagasa[i]-=1
            c-=2
          else:
            continue
        else:
          return -1
      else:
        continue
    if _c==c:
      return -1
    ans+=1

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int, input().split())) for i in range(N)]
a=0
for _ in range(499500):
    l=[]
    for i in range(N):
        if A[i]!=None:
            if A[A[i][0]-1][0]==i+1:
                l.append(i)
    if l==[]:
        print(-1)
        break
    else:
        for i in l:
            del A[i][0]
            if A[i]==[]:
                A[i]=None
    a+=1
    if A==[None]*N:
        print(a)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

now = []
for i in range(n):
    now.append(a[i].popleft()-1)
    a[i].append(0)
# print(a)
# print(now)

ans = 0
battle = 0
max_battle = n*(n-1)//2
while battle < max_battle:
    checked = [False]*n
    nogame = True
    for i in range(n):
        if checked[i] or checked[now[i]] or now[i]==-1:
            continue
        checked[i] = True
        if now[now[i]]==i:
            x = i
            y = now[i]
            checked[y] = True
            now[x] = a[x].popleft()-1
            now[y] = a[y].popleft()-1
            battle += 1
            nogame = False
            # print(i, now)

    if nogame:
        print(-1)
        exit()
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

import sys
input = sys.stdin.readline


n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
                    if num >= n * (n - 1) // 2:
                        break
    if (len(visit) == 0):
        day = -1
        break
    if num >= n * (n - 1) // 2:
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_s = [] 
for i in range(n):
    a_s.append([int(item) - 1 for item in input().split()])

total = n * (n - 1) // 2
days = 0
itrs = [0] * n
fights = 0

while True:
    wants = set()
    has_match = False
    for item in range(n):
        idx = itrs[item]
        if idx == n - 1:
            continue
        want = a_s[item][idx]
        # Check there is match or not
        if a_s[want][itrs[want]] == item:
            has_match = True
            if item < want:
                wants.add((item, want))
            else:
                wants.add((want, item))
    if not has_match:
        break
    # Process match
    for a, b in wants:
        itrs[a] += 1
        itrs[b] += 1
        fights += 1
    days += 1
    if days > total:
        print(-1)
        exit()

if fights == total:
    print(days)
else:
    print(-1)