Problem:
 Score : 1000 points    Problem Statement We will call a string x  good if it satisfies the following condition:   Condition: x can be represented as a concatenation of two copies of another string y of length at least 1 .   For example, aa and bubobubo are good; an empty string, a , abcabcabc and abba are not good.  Eagle and Owl created a puzzle on good strings.
Find one string s that satisfies the following conditions. It can be proved that such a string always exists under the constraints in this problem.   1 ≤ |s| ≤ 200  Each character of s is one of the 100 characters represented by the integers 1 through 100 .  Among the 2^{|s|} subsequences of s , exactly N are good strings.       Constraints  1 ≤ N ≤ 10^{12}         Input Input is given from Standard Input in the following format:  N       Output In the first line, print |s| , the length of s .
In the second line, print the elements in s in order, with spaces in between. Any string that satisfies the above conditions will be accepted.        Sample Input 1 7      Sample Output 1 4
1 1 1 1  There are two good strings that appear as subsequences of s : (1,1) and (1,1,1,1) . There are six occurrences of (1,1) and one occurrence of (1,1,1,1) , for a total of seven.       Sample Input 2 299      Sample Output 2 23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

Solution (Python):
def test():
    from itertools import combinations

    s = '111223111223'
    result = 0
    for k in range(1, len(s) // 2 + 1):
        for idx in combinations(range(len(s)), 2 * k):
            success = True
            for ii in range(k):
                if s[idx[ii]] != s[idx[ii + k]]:
                    success = False
                    break
            if success:
                result += 1
    print(result)


n = int(input())

factorials = [1, 1]
for i in range(2, 40):
    factorials.append(factorials[-1] * i)

patterns = {}
for i in range(2, 40):
    base = (1 << (i - 1)) - 1
    gain = base
    chars = i
    if gain > n:
        break
    if gain not in patterns or chars < patterns[gain][0]:
        patterns[gain] = (chars, (i,))
    if i % 2 == 1:
        continue

    a = i // 2
    ncr1 = factorials[i] // factorials[a] // factorials[a] - 1

    for b in range(1, a + 1):
        base2 = (1 << (2 * b - 1)) - 1
        ncr2 = factorials[2 * b] // factorials[b] // factorials[b] - 1
        gain = base + base2 + ncr1 * ncr2
        chars = i + 2 * b
        if gain > n:
            break
        if gain not in patterns or chars < patterns[gain][0]:
            patterns[gain] = (chars, (a, b))

        for c in range(1, b + 1):
            base3 = (1 << (2 * c - 1)) - 1
            ncr3 = factorials[2 * c] // factorials[c] // factorials[c] - 1
            gain = base + base2 + base3 + ncr1 * ncr2 * ncr3 + ncr1 * ncr2 + ncr2 * ncr3 + ncr3 * ncr1
            chars = i + 2 * b + 2 * c
            if gain > n:
                break
            if gain not in patterns or chars < patterns[gain][0]:
                patterns[gain] = (chars, (a, b, c))

            for d in range(1, c + 1):
                base4 = (1 << (2 * d - 1)) - 1
                ncr4 = factorials[2 * d] // factorials[d] // factorials[d] - 1
                gain = base + base2 + base3 + base4 + ncr1 * ncr2 * ncr3 * ncr4
                gain += ncr1 * ncr2 * ncr3 + ncr1 * ncr2 * ncr4 + ncr1 * ncr3 * ncr4 + ncr2 * ncr3 * ncr4
                gain += ncr1 * ncr2 + ncr1 * ncr3 + ncr1 * ncr4 + ncr2 * ncr3 + ncr2 * ncr4 + ncr3 * ncr4
                chars = i + 2 * b + 2 * c + 2 * d
                if gain > n:
                    break
                if gain not in patterns or chars < patterns[gain][0]:
                    patterns[gain] = (chars, (a, b, c, d))


def dfs(use, i, remaining, total_char):
    if remaining == 0:
        return total_char <= 200

    for j in range(i, len(patterns)):
        gain, (chars, lengths) = patterns[j]
        if total_char + remaining * chars / gain > 200:
            break
        if gain > remaining:
            continue
        use.append(lengths)
        result = dfs(use, j, remaining - gain, total_char + chars)
        if result:
            return True
        use.pop()

    return False


patterns = sorted(patterns.items(), key=lambda item: item[0] / item[1][0], reverse=True)

use = []
result = dfs(use, 0, n, 0)
assert result

ans = []
c = 1
for lengths in use:
    if len(lengths) == 1:
        ans.extend([c] * lengths[0])
        c += 1
    else:
        for _ in range(2):
            for i, l in enumerate(lengths):
                ans.extend([c + i] * l)
        c += len(lengths)

print(len(ans))
print(*ans)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = bin(int(input()))[2:]
    ans = [100, 100] + list(range(1, len(N))) + list(range(1, len(N)))
    k = len(N)
    for i in range(len(N) - 1):
        if N[-i-1] == "1":
            for j in range(len(ans)):
                if ans[j] == i+1:
                    ans.insert(j, k)
                    k += 1
                    break
    ans += list(range(k-1, len(N) - 1, -1))
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""左右で文字列集合を分割する。abc bac のように、左側、右側のそれぞれでは
文字が重複しないようにして作る。"""

def f(N, i=1):
    
    if N == 1:
        return deque(), deque()
    if N % 2 == 0:
        A, B = f(N // 2, i + 1)
        A.append(i)
        B.append(i)
        return A, B
    else:
        A, B = f(N - 1, i + 1)
        A.append(i)
        B.appendleft(i)
        return A, B

N = int(read()) + 1

A, B = f(N)
S = A + B
print(len(S))
print(*S)

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.readline

A = [0]
dp = [0]
N = int(readline())

cnt = 0
while N:
    cnt += 1
    idx = len(A)
    if N >= 1+dp[-1]:
        N -= 1+dp[-1]
        A.append(cnt)
        dp.append(1+2*dp[-1])
    else:
        for l in range(len(A)):
            if N >= dp[l] + 1:
                idx = l
    
        N -= dp[idx] + 1
        dp = dp[:idx+1] + [2*dp[idx]+1] + [dp[idx]+1 + dp[i] for i in range(idx+1, len(dp))]
        A = A[:idx+1] + [cnt] + A[idx+1:]

ans = (A[1:] + list(range(1, len(A))))
print(len(ans))
print(*ans)

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''













def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 4 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


L = 25
cmb2 = [0 for i in range(L+1)]

for i in range(L+1):
    for j in range(1,i+1):
        cmb2[i] += cmb(i,j,p) * cmb(i,j,p)



cmb3 = Zeros(L+1,L+1)

for i in range(L+1):
    for j in range(L+1):
        for k in range(1,min(i,j)+1):
            cmb3[i][j] += cmb(i,k,p) * cmb(j,k,p)

element = []



for i in range(1,L+1):
    for j in range(1,L+1):
        for k in range(1,L+1):
            for l in range(1,L+1):
                element.append([ cmb3[i][k]*cmb3[j][l] + 2**((i+k)-1) + 2**((j+l)-1) - 2, i,j,k,l])

for i in range(1,L):
    element.append([2**(i-1)-1, -1, i,0,0])
element.sort(key = lambda x : x[0], reverse=True)




n = int(input())

ans = []
used = 0

while(True):
    if(n==0):
        print(len(ans))
        print(" ".join(map(str,ans)))
        break
    now = []
    for i in element:
        if(i[0]<=n):
            now = i
            break
    if(now[1]==-1):
        used += 1
        for j in range(now[2]):
            ans.append(used)
    else:
        used+=2
        for j in range(now[1]):
            ans.append(used-1)
        for j in range(now[2]):
            ans.append(used)
        for j in range(now[3]):
            ans.append(used-1)
        for j in range(now[4]):
            ans.append(used)
    n -= now[0]

Solution (Python):
n=int(input())
a=[0]
for i in range(40):
  if n&(1<<i):a.append(i)
ans=[]
j=100
for i in range(len(a)-1):
  for _ in range(a[i+1]-a[i]):
    ans.append(j)
    j-=1
  ans.append(i+1)
ans=ans[:-1]
ans=[50]+[100-i for i in range(a[-1])]+[i+1 for i in range(len(a)-2)][::-1]+ans+[50]
print(len(ans))
print(*ans)

Solution (Python):
n = int(input())
t = n.bit_length()
n -= 2 ** (t - 1) - 1
k = t
res = list(range(1, t))
for i in range(t, -1, -1):
    if (n >> i) & 1:
        res.insert(i, k)
        k += 1
print(len(res) * 2)
print(' '.join(map(str, list(range(1, k)) + res)))

Solution (Python):
def f(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return f(x >> 1,n + 1) + [n]
	else:
		return [n] + f(x - 1,n + 1)

p = f(input(),1)
p += range(len(p),0,-1)
print len(p)
print ' '.join(list(map(str,p)))

Solution (Python):
def f(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return f(x >> 1,n + 1) + [n]
	else:
		return [n] + f(x - 1,n + 1)

def g(x,n):
	if x == 1: return [n];
	if x % 2 == 1:
		return g(x >> 1,n + 1) + [n]
	else:
		return g(x - 1,n + 1) + [n]

n = input()
p = f(n,1) + g(n,1)
print len(p)
print ' '.join(list(map(str,p)))

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque

N = int(input())


N += 1

bit = [i for i in range(60) if N&(1<<i)]

n = bit[-1]
left = deque(range(n,0,-1))
right = deque()
x = n+1

for i in range(n,0,-1):
    right.append(i)
    if i-1 in bit:
        right.append(x)
        left.appendleft(x)
        x += 1

S = list(left) + list(right)
print(len(S))
print(' '.join(map(str,S)))

Solution (Python):
fact = [1]
for i in range(1, 101):
    fact.append(fact[-1]*i)
    
def C(a, b):
    return fact[a]//(fact[b]*fact[a-b])

def sC(a, b):
    ret = 0
    for i in range(min(b, a-b) + 1):
        ret += C(b, i) * C(a - b, i)
    return ret

def calc(n, k):
    if n<=0:
        return []
    i = 0
    while (1<<(i+1)) -1 <= n:
        i += 1
        
    ret = [str(k)] * (i+1)
    rem = n-((1<<i) - 1)
    kk = k + 1
    i += 1
    j = i // 2
    
    while j > 0:
        while True:
            tmp = sC(i, j)
            if tmp <= rem:
                ret.insert(j, str(kk))
                ret.append(str(kk))
                kk += 1
                rem -= tmp

            else:
                break
                
        j -= 1
        
    return ret + calc(rem, kk)

N = int(input())

X = calc(N, 1)
print(len(X))
print(" ".join(X))

Solution (Python):





"""
agc012 C
"""


n = int(input())
m = len(bin(n+1))-2
n = n-(2**(m-1)-1)


fact = []
tmp = 1
for i in range(1, m+2):
    fact.append(tmp)
    tmp = tmp*i

binom = [[0]*(m+1) for i in range(m+1)]
for i in range(m+1):
    for j in range(i+1):
        binom[i][j] = (fact[i]//(fact[j]*fact[i-j]))

binomsums = []
for j in range(m//2+1):
    tmp = 1
    for i in range(1, j+1):
        tmp += binom[j][i]*binom[m-j][i]
    binomsums.append(tmp)

a = [0]*(m//2+1)
ind = m//2
while n != 0:
    b = binomsums.pop()
    c, n = divmod(n, b)
    a[ind] = c
    ind -= 1

ans = []
i = 2
for j in range(m//2+1):
    for k in range(a[j]):
        ans.append(i)
        i += 1
    ans.append(1)
ans = ans + [1 for j in range(m-m//2-1)]
i -= 1
while i >= 2:
    ans.append(i)
    i -= 1
print(len(ans))
print(" ".join(map(str, ans)))

Solution (Python):
p,k=[],1
for i in bin(int(input())+1)[3:]:
	p+=[k]
	k+=1
	if i=='1':
		p=[k]+p
		k+=1
p+=range(1,k)
print(len(p))
print(*p)

Solution (Python):
p,q,k=[],[],1
for i in bin(int(input())+1)[3:]:
	p+=[k]
	q+=[k]
	k+=1
	if i=='1':
		p=[k]+p
		q+=[k]
		k+=1
p+=q
print(len(p))
print(*p)

Solution (Python):

n = int(input())
x = []
y = []
k = 1
for c in bin(n + 1)[2 :][1 :]:
    x += [ k ]
    y += [ k ]
    k += 1
    if int(c):
        x = [ k ] + x
        y += [ k ]
        k += 1
print(len(x + y))
print(*(x + y))

Solution (Python):


def construct(N):
    for n in range(40, -1, -1):
        if N >= (1 << n) - 1:
            break
    p = []
    for i in range(1, n+1):
        p.append(i)
    N -= (1 << n) - 1
    for i in range(n-1, -1, -1):
        if N < 1 << i:
            continue
        n += 1
        p = p[:i] + [n] + p[i:]
        N -= 1 << i
    return p

N = int(input())
part = construct(N)
ans = part + [x + 1 for x in range(len(part))]
print(len(ans))
print(*ans, end=' ')
print()

Solution (Python):
if __name__ == "__main__":
    N = int(input())
    n = 40
    for i in range(40, -1, -1):
        if (N >= (1 << i) - 1):
            n = i
            break
    data = []
    for i in range(n):
        data.append(i + 1)
    N -= (1 << n) - 1
    tmp = n
    for i in range(n - 1, -1, -1):
        if (N < (1 << i)):
            continue
        tmp += 1
        data = data[:i] + [tmp] + data[i:]
        N -= (1 << i)
    ans = []
    for x in range(len(data)):
        ans.append(x + 1)
    ans = ans + data
    print (len(ans))
    print (" ".join(map(str, ans)))

Solution (Python):


def main():
  N = int(raw_input()) + 1
  a = []
  b = 0
  for c in bin(N)[3:]:
    b += 1
    a.append(b)
    if c == '1':
      b += 1
      a = [b] + a
  a.extend(range(1, b + 1))
  print b * 2
  print ' '.join([str(x) for x in a])

if __name__ == '__main__':
  main()

Solution (Python):
from collections import deque

N = int( input() ) + 1 

hi = 0
while 1 << hi + 1 <= N:
  hi += 1
hi -= 1

ans_A = deque()
ans_B = deque()
ptr = 1
for i in range( hi, -1, -1 ):
  ans_A.append( ptr )
  ans_B.append( ptr )
  ptr += 1
  if N >> i & 1:
    ans_A.append( ptr )
    ans_B.appendleft( ptr )
    ptr += 1

print( len( ans_A ) * 2 )
for i in range( len( ans_A ) ):
  print( ans_A[ i ], end = ' ' )
for i in range( len( ans_B ) ):
  print( ans_B[ i ], end = ' \n'[ i + 1 == len( ans_B ) ] )

Solution (Python):
from collections import deque

N = int( input() ) + 1 

hi = 0
while 1 << hi + 2 <= N:
  hi += 1

ans_A = deque()
ans_B = deque()
ptr = 1
for i in range( hi, -1, -1 ):
  ans_A.append( ptr )
  ans_B.append( ptr )
  ptr += 1
  if N >> i & 1:
    ans_A.append( ptr )
    ans_B.appendleft( ptr )
    ptr += 1

print( len( ans_A ) * 2 )
for i in range( len( ans_A ) ):
  print( ans_A[ i ], end = ' ' )
for i in range( len( ans_B ) ):
  print( ans_B[ i ], end = ' \n'[ i + 1 == len( ans_B ) ] )

Solution (Python):

def f(n):
    if n == 1:
        return []
    if n % 2 == 0:
        r = f(n//2)
        k = len(r)
        return r + [k+1]
    if n % 2 == 1:
        r = f(n - 1)
        k = len(r)
        return [k+1] + r

n = int(input())
r = f(n+1)
k = len(r)
res = r + list(range(1, k+1))
print(len(res))
for x in res:
    print(x, end=' ')
print()

Solution (Python):


n = int(input()) + 1

k = 50
while ~n >> k & 1:
    k -= 1
k -= 1

a = []
b = []
now = 1
while k >= 0:
    a = a + [now]
    b = b + [now]
    now += 1

    if n >> k & 1:
        a = a + [now]
        b = [now] + b
        now += 1

    k -= 1

print(len(a + b))
print(*(a + b))

Solution (Python):
n = int(raw_input()) + 1
n = bin(n)[3:]
ra = []
rb = []
c = 1
for i in n:
    ra.append(c)
    rb.append(c)
    c += 1
    if i == '1':
        ra = ra + [c]
        rb = [c] + rb
        c += 1
res = ra + rb
print len(res)
print ' '.join(map(str, res))

Solution (Python):



def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

from copy import deepcopy
def makeTable(init, *dims):
    if 0 == len(dims): return deepcopy(init)
    return [makeTable(init, *dims[1:]) for i in xrange(dims[0])]


pascal = makeTable(None, 200, 200)

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if 0 == k or n == k:
        return 1
    if None is not pascal[n][k]:
        return pascal[n][k]

    rr = choose(n-1, k-1) + choose(n-1, k)
    pascal[n][k] = rr

    return rr



N =        int( stdin.readline().strip() )


rr = []

basis = []
for i in range(2, 30):
    here = (1 << (i-1)) - 1
    basis.append((here, [1] * i))

    for second in range(1, i+1):
        here = (1 << (i + second - 1)) - 1
        extra = 0
        for length in range(1, second+1):
            extra += choose(second, length) * choose(i, length)
        for bs in range(1, 15):
            mult = 0
            for bl in range(1, bs+1):
                mult += choose(bs, bl)**2
            basis.append((here+extra*mult + (1 << (bs*2-1))-1, [1] * i + [2]*bs + [1] * second + [2]*bs))


basis.sort()
basis.reverse()
offset = 0
for h, pattern in basis:
    while h <= N:
        N -= h
        rr.extend([p+offset for p in pattern])
        offset += 2

print len(rr)
print ' '.join(map(str, rr))

Solution (Python):
def ncr(n, r):
    r = min(n - r, r)
    up = 1
    down = 1
    for i in range(r):
        up *= (n - i)
        down *= (i + 1)
    return up // down


def seq(x):
    s = 0
    for i in range(1, x):
        j = i * 2
        if j > x:
            break
        s += ncr(x, j)
    return s


def ins(total, p):
    s = 0
    for i in range(p + 1):
        s += ncr(p, i) * ncr(total - p, i)
    return s

ans = []
N = int(input())
k = 1

for i in range(41, 0, -1):
    x = seq(i)
    if N >= x:
        for j in range(i):
            ans.append(k)
        N -= x
        k += 1
        break

size = len(ans)
s = size // 2
while N > 90:
    m = 0
    t = 0
    for i in range(s + 1):
        tmp = ins(size, i)
        if tmp > N:
            break
        if tmp > t:
            t = tmp
            m = i
    N -= t
    ans.insert(m, k)
    ans.append(k)
    k += 1

while N > 0:
    for i in range(41, 0, -1):
        x = seq(i)
        if N >= x:
            for j in range(i):
                ans.append(k)
            N -= x
            k += 1
            break
print(len(ans))
print(" ".join([str(x) for x in ans]))

Solution (Python):
def nCr(a,b):
	tmp=1
	for i in range(a,a-b,-1):tmp*=i
	for i in range(1,b+1,1):tmp//=i
	return tmp

n=int(input())
out=[]
co=1
coo=0
while n>0:
	t=2
	while True:
		sum1=0
		for j in range(2,t+1,2):
			sum1+=nCr(t,j)

		if n<sum1:
			t-=1

			break
		rco=sum1
		t+=1
	ad=[co for _ in range(t)]
	sum1=rco
	ma=sum1

	for toa in range(1,4):
		for tob in range(1,4):
			CO=0
			for r in range(1,min(toa,tob)+1):
				CO+=nCr(toa,r)*nCr(tob,r)
		
			for a in range(1,t):
				sum2=sum1+((2**(toa+tob-1))-1)
				for b in range(1,a+1):
					sum2+=nCr(a,b)*nCr(t-a,b)*CO
				if sum2>n:continue
				if ma<sum2:
					ma=sum2
					ad=[co for _ in range(a)]
					for _ in range(toa):ad.append(100-coo)
					for _ in range(t-a):ad.append(co)
					for _ in range(tob):ad.append(100-coo)
	

	for t in ad:out.append(t)

	n-=ma
	coo+=1
	co+=1
print(len(out))
print(*out)

Solution (Python):
from sys import stdin
while True:
    s = stdin.readline()
    if not s:
        break
    n = int(s)
    a = [] 
    b = []
    f = []
    for i in xrange(60):
        f.append(2**i)
    bi = [] 
    s = 0 
    cur = 59 
    while cur>=0:
        if f[cur ]-1 <=n:
            break 
        cur -= 1 
    hi = cur
    done = 2**hi - 1 
    for u in xrange(1,hi+1):
        b.append(u)
    co = 1 
    nn = n 
    n -= done 
    while cur >=1 :
        a.append(cur)
        if f[cur-1]<= n:
            hi += 1 
            a.append(hi)
            b.append(hi)
            n-= f[cur-1]
        
        cur -=1 
    a.reverse()
    c =  a + b 
    print  len(c)
    for i in c:
        print i,
    print ""