Submission #1302645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302645		akshar_7	Longest beautiful sequence (IZhO17_subsequence)	Pypy 3	100 / 100	5244 ms	162568 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 i in range(1<<k):
  for j in range(1<<k):
    for l in range(k+1):
      bit_cnt[i][j] += ((i&j)>>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 = 0
      for l in range(nb):
        if (a[i]&a[j])&1<<l:
          bc +=1
      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 44%)

=======

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