結果
問題 |
No.1804 Intersection of LIS
|
ユーザー |
![]() |
提出日時 | 2022-01-09 12:42:04 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,763 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 193,916 KB |
最終ジャッジ日時 | 2024-11-14 10:20:51 |
合計ジャッジ時間 | 10,494 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 30 |
ソースコード
import sys #input = sys.stdin.readline #文字列につけてはダメ input = sys.stdin.buffer.readline #文字列につけてはダメ #sys.setrecursionlimit(1000000) import bisect #import itertools #import random #from heapq import heapify, heappop, heappush #from collections import defaultdict #from collections import deque #import copy #from functools import lru_cache def LIS(N, A): #狭義単調増加部分列 INF = float("inf") #dp[i]: 最長増加部分列がi個の時の最後の値の最小値 dp = [INF]*(N+1) dp[0] = -INF #iは1indexなので0の時は適当な値(-INF)を入れている。 last_change = [INF]*(N+1) for i,x in enumerate(A): idx = bisect.bisect_left(dp, x) #x未満の数字を探して更新。 dp[idx] = x #min(x, dp[idx]) last_change[idx] = i #print(last_change) #ここが最長となるときの最後の更新 last = bisect.bisect_left(last_change,INF) - 1 last_idx = last_change[last] #print("last",last_idx) ndp = [INF]*(N+1) ndp[0] = -INF #iは1indexなので0の時は適当な値(-INF)を入れている。 kouho = [set([]) for _ in range(N+1)] for i in range(last_idx+1): x = A[i] #print("x",x) idx = bisect.bisect_left(ndp, x) #x未満の数字を探して更新。 ndp[idx] = x #min(x, dp[idx]) kouho[idx].add(x) return kouho #INF未満となるIndexを返す。 def main(): n = int(input()) P = list(map(int,input().split())) ret = LIS(n,P) #print(ret) ans = [] for S in ret: if len(S) == 1: temp = list(S); temp = temp[0] ans.append(temp) print(len(ans)) print(*ans) if __name__ == '__main__': main()