結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Sinonen
提出日時 2025-11-17 19:45:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,629 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 199 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 86,292 KB
最終ジャッジ日時 2025-12-06 23:30:57
合計ジャッジ時間 8,393 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 76
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import random
T = int(input())

def solve(N):
	inv_path = [-1] * N
	path = [-1] * N
	I = random.randint(0, N - 1)
	P = [-1] * N
	cnt = 0
	for i in range(N):
		if i == I:
			continue
		print(1, i + 1, I + 1)
		k = int(input())
		if k == -1:
			cnt += 1
			continue
		path[i] = k - 1
		inv_path[k - 1] = i
	check = 1
	if path == [-1] * N:
		P[I] = N
		check = 0
	elif cnt == 1:
		P[I] = 1
		start = -1
		for i in range(N):
			if i == I:
				continue
			if inv_path[i] == -1:
				start = i
		P[start] = 2
		c = 2
		while  path[start] != -1:
			start = path[start]
			c += 1
			P[start] = c
		return P
	else:
		ok = 1
		for i in range(N):
			if path[i] != -1:
				if path[path[i]] != -1:
					ok = 0
		P[I] = cnt + ok
	#print(P,path,inv_path)
	if check == 0:
		I = (I + 1) % N
		cnt = 0
		for i in range(N):
			if i == I:
				continue
			print(1, i + 1, I + 1)
			k = int(input())
			if k == -1:
				cnt += 1
				continue
			path[i] = k - 1
			inv_path[k - 1] = i
		check = 1
		if path == [-1] * N:
			P[I] = N
			check = 0
		elif cnt == 1:
			P[I] = 1
			start = -1
			for i in range(N):
				if i == I:
					continue
				if inv_path[i] == -1:
					start = i
			P[start] = 2
			c = 2
			while  path[start] != -1:
				start = path[start]
				c += 1
				P[start] = c
			return P
		else:
			ok = 1
			for i in range(N):
				if path[i] != -1:
					if path[path[i]] != -1:
						ok = 0
			P[I] = cnt + ok
	else:
		A = []
		b = -1
		for i in range(N):
			if i == I:
				continue
			if path[i] == -1:
				b = i
			elif inv_path[i] == -1:
				A.append(i)
		#print(A, b)
		for i in range(len(A)):
			a = A[i]
			while True:
				print(1, a + 1, b + 1)
				k = int(input())
				if k == -1:
					break
				b = k - 1
		P[b] = N
	#print(*P)
	I = -1
	J = -1
	A = []
	for i in range(N):
		if inv_path[i] == -1:
			A.append(i)
	for i in range(N):
		if P[i] == N:
			I = i
		elif P[i] != -1:
			J = i
	K = I
	while inv_path[K] != -1:
		K = inv_path[K]
	#print(I, J, K, P, path, inv_path)
	P[K] = N % P[J]
	inv_path2 = [-1] * N
	for j in range(len(A)):
		if A[j] == K:
			continue
		#print(1, A[j] + 1, K + 1)
		k = int(input())
		k -= 1
		c = 0
		while inv_path[k] != -1:
			k = inv_path[k]
			c += 1
		if c >= 2:
			P[A[j]] = 2 * P[J]
			continue
		inv_path2[k] = A[j]
	now = K
	nowP = P[K]
	#print(P, inv_path2)
	while inv_path2[now] != -1:
		now = inv_path2[now]
		nowP = (nowP - P[K]) % P[J]
		if nowP == 0:
			nowP = P[J]
		P[now] = nowP
	for i in range(len(A)):
		now = A[i]
		nowP = P[A[i]]
		while path[now] != -1:
			now = path[now]
			nowP = nowP + P[J]
			P[now] = nowP
	return P
		
for _ in range(T):
	N = int(input())
	print(2, *solve(N))
0