Submission #1302650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302650		akshar_7	Longest beautiful sequence (IZhO17_subsequence)	Pypy 3	100 / 100	2675 ms	159956 KiB

subsequence

from sys import stdin
input = stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
nb = 20
k = nb>>1
mask = (1<<k)-1
bit_cnt = [0]*(1<<k)
for i in range(1<<k):
  for l in range(k+1):
    bit_cnt[i] += (i>>l)&1
best = [0]*((1<<k)*(1<<k)*(k+1))
dp = [0]*n
ans = [0]*n
for j in range(n):
  m = a[j]
  x,y = mask&m, m>>k
  prev = 0
  for i in range(1<<k):
    cl = bit_cnt[i&x]
    cr = b[j]-cl
    if 0<=cr<=10:
      prev = max(prev, best[cr<<(2*k) |y<<k |i])
  dp[j] = prev+1
  for i in range(1<<k):
    cr = bit_cnt[i&y]
    best[cr<<(2*k) |i<<k |x] = max(prev+1, best[cr<<(2*k) |i<<k |x])
res = max(dp)
print(res)
ans = []
j = -1
for i in range(n-1, -1, -1):
  if res==dp[i]:
    if j==-1:
      j=i; res-=1
      ans.append(i+1)
    else:
      bc = bit_cnt[a[i]&a[j]&mask] + bit_cnt[(a[i]>>k)&(a[j]>>k)]
      if bc==b[j]:
        ans.append(i+1)
        j=i; res-=1
print(*ans[::-1])

Compilation message (stdout)

Compiling 'subsequence.py'...

=======
  adding: __main__.pyc (deflated 42%)

=======

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60