結果
問題 |
No.3086 Re One Two
|
ユーザー |
![]() |
提出日時 | 2025-04-04 21:49:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 284 ms / 2,000 ms |
コード長 | 4,957 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 82,892 KB |
実行使用メモリ | 125,560 KB |
最終ジャッジ日時 | 2025-04-04 21:49:57 |
合計ジャッジ時間 | 9,637 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import sys, math sys.setrecursionlimit(10**8) sys.set_int_max_str_digits(0) INF = 10**18 MOD = 998244353 from bisect import bisect_left, bisect_right from collections import deque, defaultdict, Counter from itertools import product, combinations, permutations, groupby, accumulate from heapq import heapify, heappop, heappush def I(): return sys.stdin.readline().rstrip() def II(): return int(sys.stdin.readline().rstrip()) def IS(): return sys.stdin.readline().rstrip().split() def MII(): return map(int, sys.stdin.readline().rstrip().split()) def LI(): return list(sys.stdin.readline().rstrip()) def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split())) def LII(): return list(map(int, sys.stdin.readline().rstrip().split())) def LSI(): return list(map(str, sys.stdin.readline().rstrip().split())) def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())) def kiriage(a, b): return (a+b-1)//b #def check(i:int, j:int): return 0 <= i < H and 0 <= j < W class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n self.link = [i for i in range(n)] self.L = list(range(n)) self.R = list(range(n)) self.score = [0] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): rootx = self.find(x) rooty = self.find(y) if rootx == rooty: # すでに same ならなにもしない! return if self.parents[rootx] > self.parents[rooty]: # -3 > -4 のようなケース(前者の方が軍勢が少ない) rootx, rooty = rooty, rootx # rootx = 多い, rooty = 少ない の順番に変更 # 統合(rootx が新しい棟梁, rooty は軍門に下った) self.parents[rootx] += self.parents[rooty] # 多い方(rootx)に併合する self.parents[rooty] = rootx self.link[x], self.link[y] = self.link[y], self.link[x] self.L[rootx] = min(self.L[rootx], self.L[rooty]) self.R[rootx] = max(self.R[rootx], self.R[rooty]) self.score[rootx] += self.score[rooty] self.score[rooty] = 0 def size(self, x): # O(1) return -self.parents[self.find(x)] def same(self, x, y): # O(1) return self.find(x) == self.find(y) def members(self, x): # O(K: 集合の要素数) 最小で1、最大でN res = [x] now = self.link[x] while now != x: res.append(now) now = self.link[now] return res def get_LR(self, x): x = self.find(x) return (self.L[x], self.R[x]) def roots(self): # O(N) return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): # roots() の呼び出しは全頂点の par をチェックする=遅いため、N回使うと TLE する return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def cnt_ika(li, x): # x 以下の要素数 return bisect_right(li, x) def cnt_miman(li, x): # x 未満の要素数 return bisect_left(li, x) def cnt_ijou(li, x): # x 以上の要素数 return len(li) - cnt_miman(li, x) def cnt_choka(li, x): # x より大きい要素数 return len(li) - cnt_ika(li, x) def num_ika(li, x): # x 以下の最大値(なければ -inf) res = bisect_right(li, x) - 1 return -INF if res == -1 else li[res] def num_miman(li, x): # x 未満の最大値(なければ -inf) res = bisect_left(li, x) - 1 return -INF if res == -1 else li[res] def num_ijou(li, x): # x 以上の最小値(なければ inf) res = bisect_left(li, x) return INF if res == len(li) else li[res] def num_choka(li, x): # x より大きい最小値(なければ inf) res = bisect_right(li, x) return INF if res == len(li) else li[res] N = II() A, B = [], [] B_1 = [] B_2 = [] for i in range(N): a, b = MII() A.append(a) B.append(b) if b == 1: B_1.append(i) if b == 2: B_2.append(i) uf = UnionFind(N) # A は前から見る for i in range(N - 1): a = A[i] if a == 1: uf.union(i, i + 1) # Bi == 2 目線で考える for idx in B_2: idx_partner = num_choka(B_1, idx) if idx != INF: uf.union(idx, idx_partner) ansl = [] for i in range(N): if uf.size(i) == 1: ansl.append(i + 1) else: l_idx, r_idx = uf.get_LR(i) if r_idx == i: # そのCC を大きい順から答えに追加 memo = [] for member in uf.members(i): memo.append(member + 1) memo.sort(reverse=True) ansl.extend(memo) print(*ansl, sep='\n')