結果

問題 No.2178 Payable Magic Items
ユーザー MasKoaTSMasKoaTS
提出日時 2022-08-05 17:32:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,211 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 264,724 KB
最終ジャッジ日時 2024-05-08 13:15:50
合計ジャッジ時間 6,551 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 38 ms
52,672 KB
testcase_03 AC 38 ms
53,424 KB
testcase_04 AC 37 ms
52,616 KB
testcase_05 AC 38 ms
52,864 KB
testcase_06 WA -
testcase_07 AC 38 ms
54,480 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 1,009 ms
121,748 KB
testcase_20 AC 81 ms
76,748 KB
testcase_21 AC 164 ms
80,224 KB
testcase_22 AC 204 ms
81,824 KB
testcase_23 AC 96 ms
76,904 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 1,404 ms
142,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# test

import sys
input = sys.stdin.readline

class Vector:
	def __init__(self, vec):
		self.vec = vec
		self.n = len(vec)

	
def comp(one: Vector, other: Vector):
	ret = -1
	if all(a == b for a,b in zip(one.vec, other.vec)):
		ret = 0
	elif all(a <= b for a,b in zip(one.vec, other.vec)):
		ret = 1
	elif all(a >= b for a,b in zip(one.vec, other.vec)):
		ret = 2
	return ret


def qsort(veclis):
	global vector_graph
	n = len(veclis)
	if(n <= 1):
		return veclis

	pivot = Vector(veclis[n >> 1].vec)
	left = []
	right = []
	cnt = 0
	for v in veclis:
		cp = comp(v, pivot)
		if(cp == 1):
			vector_graph[dic[v.vec]].append(dic[pivot.vec])
			left.append(v)
		elif(cp == 2):
			vector_graph[dic[pivot.vec]].append(dic[v.vec])
			right.append(v)
		elif(cp == -1):
			right.append(v)
		else:
			cnt += 1

	left = qsort(left)
	right = qsort(right)
	return left + [pivot]*cnt + right


N, K = map(int, input().split())
lis = [Vector(tuple(map(int,input().split()))) for _ in [0] * N]

dic = {}
dsize = 0
for v in lis:
	if(v.vec in dic):
		continue
	dic[v.vec] = dsize
	dsize += 1
vector_graph = [[] for _ in [0] * dsize]

lis = qsort(lis)
#print(vector_graph)
ans = sum(len(l) > 0 for l in vector_graph)
print(ans)
0