Submission #53690682

Source Code Expand

"""
<方針>
- 公式解説通りです．
"""

from bisect import bisect_left

# caseの数
T = int(input())

# case毎
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  
  # 左方向からLIS
  ls = []
  L = [0]*N
  for i in range(N):
    index = bisect_left(ls, A[i])
    if(index<len(ls)):
      ls[index] = A[i]
    else:
      ls.append(A[i])
    L[i] = index+1
  
  # 右方向からLIS
  ls = []
  R = [0]*N
  for i in reversed(range(N)):
    index = bisect_left(ls, -A[i])
    if(index<len(ls)):
      ls[index] = -A[i]
    else:
      ls.append(-A[i])
    R[i] = index+1
  
  # l+r-1==LISとなる部分を探す
  ans = []
  for i in range(N):
    if(L[i]+R[i]-1==len(ls)):
      ans.append(i+1)
      
  # 出力
  print(len(ans))
  print(*ans)

Submission Info

Submission Time
Task F - Useless for LIS
User mattsunkun
Language Python (PyPy 3.10-v7.3.12)
Score 525
Code Size 830 Byte
Status AC
Exec Time 480 ms
Memory 120432 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 2
AC × 46
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 02_hand_00.txt, 02_hand_01.txt, 02_hand_02.txt, 02_hand_03.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 56 ms 76580 KiB
00_sample_01.txt AC 57 ms 76612 KiB
01_random_00.txt AC 480 ms 84308 KiB
01_random_01.txt AC 285 ms 85240 KiB
01_random_02.txt AC 267 ms 84540 KiB
01_random_03.txt AC 191 ms 84844 KiB
01_random_04.txt AC 183 ms 84704 KiB
01_random_05.txt AC 155 ms 117296 KiB
01_random_06.txt AC 162 ms 117284 KiB
01_random_07.txt AC 159 ms 117288 KiB
01_random_08.txt AC 159 ms 117240 KiB
01_random_09.txt AC 161 ms 116908 KiB
01_random_10.txt AC 470 ms 84176 KiB
01_random_11.txt AC 266 ms 84468 KiB
01_random_12.txt AC 276 ms 85320 KiB
01_random_13.txt AC 179 ms 84468 KiB
01_random_14.txt AC 180 ms 84764 KiB
01_random_15.txt AC 155 ms 114656 KiB
01_random_16.txt AC 157 ms 114660 KiB
01_random_17.txt AC 161 ms 114764 KiB
01_random_18.txt AC 158 ms 114064 KiB
01_random_19.txt AC 153 ms 113692 KiB
01_random_20.txt AC 474 ms 84556 KiB
01_random_21.txt AC 264 ms 84656 KiB
01_random_22.txt AC 244 ms 85052 KiB
01_random_23.txt AC 204 ms 84648 KiB
01_random_24.txt AC 181 ms 84976 KiB
01_random_25.txt AC 147 ms 112552 KiB
01_random_26.txt AC 149 ms 112120 KiB
01_random_27.txt AC 148 ms 112204 KiB
01_random_28.txt AC 150 ms 112208 KiB
01_random_29.txt AC 138 ms 111936 KiB
01_random_30.txt AC 153 ms 115076 KiB
01_random_31.txt AC 173 ms 114708 KiB
01_random_32.txt AC 155 ms 115120 KiB
01_random_33.txt AC 177 ms 115244 KiB
01_random_34.txt AC 174 ms 114788 KiB
01_random_35.txt AC 177 ms 114832 KiB
01_random_36.txt AC 153 ms 114804 KiB
01_random_37.txt AC 166 ms 114564 KiB
01_random_38.txt AC 155 ms 114788 KiB
01_random_39.txt AC 153 ms 114820 KiB
02_hand_00.txt AC 57 ms 76452 KiB
02_hand_01.txt AC 134 ms 112084 KiB
02_hand_02.txt AC 151 ms 120432 KiB
02_hand_03.txt AC 139 ms 114448 KiB