結果

問題 No.2178 Payable Magic Items
コンテスト
ユーザー MasKoaTS
提出日時 2022-08-05 17:32:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,211 bytes
コンパイル時間 380 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 407,148 KB
最終ジャッジ日時 2024-12-14 17:31:25
合計ジャッジ時間 40,766 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 9 WA * 8 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

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