Problem:


Score : 600 points

Problem Statement

We have one slime.

You can set the health of this slime to any integer value of your choice.

A slime reproduces every second by spawning another slime that has strictly less health. You can freely choose the health of each new slime. The first reproduction of our slime will happen in one second.

Determine if it is possible to set the healths of our first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals a multiset S.

Here S is a multiset containing 2^N (possibly duplicated) integers: S_1,~S_2,~...,~S_{2^N}.

Constraints

All values in input are integers.

1 \leq N \leq 18

1 \leq S_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 ... S_{2^N}

Output

If it is possible to set the healths of the first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals S, print Yes; otherwise, print No.

Sample Input 1

2
4 2 3 1

Sample Output 1

Yes

We will show one way to make the multiset of the healths of the slimes that will exist in 2 seconds equal to S.

First, set the health of the first slime to 4.

By letting the first slime spawn a slime whose health is 3, the healths of the slimes that exist in 1 second can be 4,~3.

Then, by letting the first slime spawn a slime whose health is 2, and letting the second slime spawn a slime whose health is 1, the healths of the slimes that exist in 2 seconds can be 4,~3,~2,~1, which is equal to S as multisets.

Sample Input 2

2
1 2 3 1

Sample Output 2

Yes

S may contain multiple instances of the same integer.

Sample Input 3

1
1 1

Sample Output 3

No

Sample Input 4

5
4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

Sample Output 4

No



Sample input:
2
4 2 3 1


Sample output:
Yes

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    グラフ，2^i区切りで見ていって，親を決める．
    BFSで上から大きい数字を振っていく=>ダメっぽい
    なんかもっと単純に，今いるやつと，残りを持っておくか=>ただ順に見ていくだけだと後回しができないので，
    作れる中で最大も数字を作る
    """

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################

    ssl=SquareSkipList(square=2000)
    
    mod=10**9+7
    N2=I()
    N=pow(2,N2)
    S=LI()
    S.sort(reverse=True)
    L=[S[0]]
    
    for i in range(1,N):
        ssl.add(S[i])
        
    ssl.add(-1) # 番兵
    
    flag=1
    while True:
        temp=[]
        for val in L:
            nxt=ssl.search_lower(val)
            if nxt==-1:
                flag=0
                break
            ssl.remove(nxt)
            temp.append(nxt)

        if flag==0:
            break    
        L+=temp
        L.sort(reverse=True)
        if len(L)==N:
            break
    
    if flag:
        print("Yes")
    else:
        print("No")

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
S=list(map(int,input().split()))
S.sort()
sl=[S.pop()]
for _ in range(N):
    stack=[]
    for i in range(len(sl)):
        x=sl[i]
        while S:
            y=S.pop()
            if y<x:
                sl.append(y)
                break
            else:
                stack.append(y)
        else:
            print('No')
            exit()
    S.extend(stack[::-1])
    sl.sort(reverse=1)
print('Yes')

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    al = [False]*(2**n)
    al[0] = True
    for i in range(n):
        usd = deque()
        cnt = 2**i
        for j,sj in enumerate(s):
            if al[j]:
                usd.append(sj)
            elif usd[0] > sj:
                usd.popleft()
                al[j] = True
                cnt -= 1
                if not cnt:
                    break
        if cnt != 0:
            print("No")
            exit()
    print("Yes")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
S = list(map(int, input().split()))
S.sort(reverse=True)
used = [False] * (2**N)
used[0] = True
for r in range(N):
    cur = deque()
    rem = 2**r
    for i in range(2**N):
        if used[i]:
            cur.append(S[i])
        elif cur and cur[0] > S[i]:
            cur.popleft()
            used[i] = True
            rem -= 1
            if rem == 0:
                break
    if rem > 0:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    N = int(input())
    Ss = list(map(int, input().split()))

    Ss.sort(reverse=True)

    Qs = [deque() for _ in range(N+1)]
    Qs[0].append(10**10)

    for S in Ss:
        for day in range(N+1):
            if not Qs[day]: continue
            if Qs[day][0] > S:
                Qs[day].popleft()
                for d in range(day+1, N+1):
                    Qs[d].append(S)
                break
        else:
            return False

    return True


if solve():
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    n = int(input())
    c = list(map(lambda p: p[1], sorted(Counter(int(si) for si in input().split()).items())))
    if c[-1] != 1:
        print('No')
        return
    c.pop()
    dp = [0] * (n + 1)
    dp[0] = 1
    for cnt in reversed(c):
        dp_next = [0] * (n + 1)
        for j in range(n):
            consume = dp[j] if dp[j] < cnt else cnt
            cnt -= consume
            dp_next[j] += dp[j] - consume
            dp_next[j + 1] += consume
            dp[j + 1] += consume
        if cnt != 0:
            print('No')
            return
        dp = dp_next
    print('Yes')
    return

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq

N=int(input())
S=list(map(int,input().split()))
S=[-S[i] for i in range(len(S))]
heapq.heapify(S)
que=[]
next=[]
rest=[]
x=heapq.heappop(S)
heapq.heappush(que,x)
while S:
    while que:
        x=heapq.heappop(que)
        while S:
            y=heapq.heappop(S)
            if y>x:
                heapq.heappush(next,x)
                heapq.heappush(next,y)
                break
            else:
                heapq.heappush(rest,y)
        else:
            print("No")
            exit()
    que=next
    next=[]
    while rest:
        x=heapq.heappop(rest)
        heapq.heappush(S,x)


print("Yes")

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Submission status: Accepted

Solution code:
from random import random


class TreapNode:
    """Treapのノード定義
    メンバ変数: 値、優先度、親へのポインタ、左右の子へのポインタ"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None


class Treap:
    """平衡二分探索木: 値の検索、挿入、削除などクエリ処理をO(logN)で実行する"""
    def __init__(self, is_multiset=False):
        self.is_multiset = is_multiset
        self.root = None

    def search(self, val: int) -> bool:
        """値の検索: 集合に値valを持つノードが存在するか"""
        ptr = self.root
        while ptr is not None:
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                return True
        return False

    def insert(self, val: int) -> bool:
        """値の削除: 集合に値valを持つノードを挿入する"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if val == ptr.val and not self.is_multiset:
                    return False
                elif ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        # 木の回転によってヒープ性を保つ
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self._rotate_left(ptr.parent)
            else:
                self._rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
        return True

    def delete(self, val: int) -> True:
        """値の削除: 集合から値valを持つノードを削除する"""
        if self.root is None:
            return False

        ptr = self.root         
        while True: 
            if ptr is None:
                return False
            elif val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                break

        # 木の回転によって削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self._rotate_left(ptr)
            elif ptr.right is None:
                self._rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self._rotate_right(ptr)
            else:
                self._rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent

        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def _rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def _rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_min(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.left
        return ret

    def search_max(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.right
        return ret

    def search_le(self, val: int):
        """val以下の最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val <= val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_lt(self, val: int):
        """valよりも小さいの最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val < val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_ge(self, val: int):
        """val以上の最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret
      
    def search_gt(self, val: int):
        """valよりも大きい最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val > val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret
      
      
n = int(input())
s = list(map(int, input().split()))
s = sorted(s, reverse=True)

tp = Treap(is_multiset=True)
used = [False] * (1 << n)
tp.insert(s[0])
used[0] = True

for step in range(n):
    cnt = 1 << step
    res = []
    for i in range(1 << n):
        if used[i]:
            continue
        val = tp.search_gt(s[i])
        if val is not None:
            cnt -= 1
            res.append(val)
            res.append(s[i])
            tp.delete(val)
            used[i] = True
        if cnt == 0:
            for val in res:
                tp.insert(val)
            break
    else:
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S.sort(reverse=True)

slimes = [S[0]]
INF = S[0] + 1
S[0] = INF
num = 1
min_idx = 1
for i in range(N):
  slimes.sort()
  n = num
  idx = min_idx
  is_continuous = True
  while n and idx<=N2-1:
    if S[idx] < slimes[n-1]:
      slimes.append(S[idx])
      S[idx] = INF
      idx += 1
      n -= 1
      min_idx += is_continuous
    else:
      if S[idx] < INF:
        is_continuous = False
      idx += 1
      min_idx += is_continuous
  
  if n:
    print('No')
    quit()
  
  num *= 2

print('Yes')

Submission status: Accepted

Solution code:
N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S.sort(reverse=True)

slimes = [S[0]]
S[0] = float('inf')
num = 1
min_idx = 1
for i in range(N):
  slimes.sort()
  n = num
  idx = min_idx
  is_continuous = True
  while n and idx<=N2-1:
    if S[idx] < slimes[n-1]:
      slimes.append(S[idx])
      S[idx] = float('inf')
      idx += 1
      n -= 1
      min_idx += is_continuous
    else:
      if S[idx] < float('inf'):
        is_continuous = False
      idx += 1
      min_idx += is_continuous
  
  if n:
    print('No')
    quit()
  
  num *= 2

print('Yes')

Submission status: Accepted

Solution code:
N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S.sort(reverse=True)

slimes = [S[0]]
S[0] = float('inf')
num = 1
for i in range(N):
  slimes.sort()
  n = num
  idx = 0
  while n and idx<=N2-1:
    if S[idx] < slimes[n-1]:
      slimes.append(S[idx])
      S[idx] = float('inf')
      idx += 1
      n -= 1
    else:
      idx += 1
  
  if n:
    print('No')
    quit()
  
  num *= 2

print('Yes')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from copy import deepcopy


def main():
    n = int(input())
    s = list(map(int, input().split()))

    left = []
    for e in s:
        heappush(left, -e)
    mx = heappop(left)

    made = []
    heappush(made, mx)

    for _ in range(n):
        made_prev = deepcopy(made)
        tmp = []

        while made_prev:
            made_val = heappop(made_prev)
            while left and left[0] <= made_val:
                pp = heappop(left)
                tmp.append(pp)

            if not left:
                print("No")
                exit()

            left_val = heappop(left)
            heappush(made, left_val)

        for e in tmp:
            heappush(left, e)

    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    visited = [False]*(2**n)
    visited[0] = 0
    now = [a[0]]
    for i in range(n):
        new = []
        now2 = 0
        for j, i in enumerate(a):
            if visited[j]:
                continue
            if now[now2] > i:
                now2 += 1
                new += [i]
                visited[j] = True
                if now2 == len(now):
                    now += new
                    now.sort(reverse=True)
                    break
        else:
            print("No")
            return

    print("Yes")


main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
S = list(map(int,input().split()))
#N = 18
#S = list(range(1,2**N+1))

def solve():
    global S
    S += [0]
    count = Counter(S)
    S = sorted(S)
    T = sorted(list(set(S)))
    M = len(T)
    pre = {T[i]:T[i-1] if i > 0 else 0 for i in range(M)}

    l = [S[-1]]
    count[S[-1]] -= 1

    while len(l) < 2**N:
        for n in l[:]:
            m = pre[n]
            pl = []
            while count[m] == 0:
                pl.append(m)
                m = pre[m]
            if pl:
                pre[n] = m
                for p in pl:
                    pre[p] = m
            if m == 0:
                print('No')
                exit()
            l.append(m)
            count[m] -= 1

    print('Yes')
    #print(count)

solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)

class SegTree:
  def segfunc(self, x, y):
    if x[0] >= y[0]: return x
    return y
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

x = pow(2, N)
table = [0] * pow(2, N)
for i in range(pow(2, N)):
  ng = 0
  ok = x
  while ok - ng > 1:
    m = (ok + ng) // 2
    if a[i] > a[m]: ok = m
    else: ng = m
  table[i] = ok

#print(table)
seg = SegTree(x, (0, N), [(a[i], i) for i in range(x)])
tt = [0]
for i in range(N):
  t = pow(2, i)
  tt.sort(reverse = True)
  ttt = []
  for j in tt:
    #print(tt)
    if table[j] >= x:
      print("No")
      exit(0)
    y, k = seg.query(table[j], x)
    if a[j] <= y or (y == 0):
      print("No")
      exit(0)
    seg.update(k, (0, N))
    ttt.append(k)
  tt += ttt
print("Yes")

Submission status: Accepted

Solution code:
import math
def cmb(n,r):
  return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
n=int(input())
a=list(map(int,input().split()))
a.sort()
ls=[0]
cnt=0
for i in range(1,2**n):
  if a[i]>a[i-1]:
    cnt+=1
  ls.append(cnt)
lmt = []
for i in range(n+1):
  lmt.extend([i]*cmb(n,i))
bias = ls[-1]-lmt[-1]
jdg = 0
ulmt = 0
for i in range(n):
  jdg += ls.count(i)
  ulmt += 2**(n-i-1)
  if jdg > ulmt:
    print("No")
    exit()
for x,l in zip(ls,lmt):
  if x-l > bias:
    print("No")
    break
else:
  print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
M = 2**N
A = list(map(int,input().split()))
A.sort(reverse=True)

ar = [A[0]]
A[0] = -1
for _ in range(N):
    ar.sort(reverse=True)
    br = []
    i = 0
    while i < M and len(br) < len(ar):
        if A[i] >= 0:
            if ar[len(br)] > A[i]:
                br.append(A[i])
                A[i] = -1
        i += 1
    if len(br) < len(ar):
        print('No')
        exit()
    ar += br
print('Yes')

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

def solve():
    N = int(input())
    Ss = list(map(int, input().split()))

    Ss.sort(reverse=True)
    pow2s = [2**i for i in range(N)]

    PQs = [[-Ss[0]] for _ in range(N)]
    nums = [0] * N
    tm0 = 0
    for S in Ss[1:]:
        for tm in range(tm0, N):
            if nums[tm] >= pow2s[tm]:
                tm0 = tm
            else:
                if -PQs[tm][0] > S:
                    heappop(PQs[tm])
                    nums[tm] += 1
                    for i in range(tm+1, N):
                        heappush(PQs[i], -S)
                    break
        else:
            return False

    return True

if solve():
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import Counter
from heapq import heapify, heappush, heappop

def solve():
    N = int(input())
    Ss = list(map(int, input().split()))

    cnt = Counter(Ss)

    PQ = [-N]
    for key in sorted(cnt.keys(), reverse=True):
        num = cnt[key]
        if len(PQ) < num:
            return False
        depths = []
        for _ in range(num):
            depths.append(-heappop(PQ))
        for depth in depths:
            for d in range(depth):
                heappush(PQ, -d)

    return True

if solve():
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
def main():
    import heapq

    n=int(input())
    A=list(map(int,input().split()))
    A.sort(reverse=True)

    timelist=[] #ステージが代わるごとに更新
    importlist=[0]
    before=A[0]
    flag=True

    for a in A[1:]:
        if before!=a: #世代交代 importlistをtimelistに追加
            for v in importlist:
                if v<n:
                    heapq.heappush(timelist,v)
            importlist=[]
        before=a
        if len(timelist)!=0:
            v=heapq.heappop(timelist)
            if v<n:
                heapq.heappush(timelist,v+1)
            else:
                flag=False
                break
            importlist.append(v+1)
        else:    
            flag=False
            break
    print("Yes" if flag else "No")
main()

Submission status: Accepted

Solution code:
import heapq

n=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)

timelist=[] #ステージが代わるごとに更新
importlist=[0]
before=A[0]
flag=True

for a in A[1:]:
    if before!=a: #世代交代 importlistをtimelistに追加
        for v in importlist:
            if v<n:
                heapq.heappush(timelist,v)
        importlist=[]
    before=a
    if len(timelist)!=0:
        v=heapq.heappop(timelist)
        if v<n:
            heapq.heappush(timelist,v+1)
        else:
            flag=False
            break
        importlist.append(v+1)
    else:    
        flag=False
        break
print("Yes" if flag else "No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort(reverse=1)
cur = [A[0]]
nxt = cur[:]
# 作成済を-1とする
A[0] = -1

for _ in range(N):
    j = 0
    for i, a in enumerate(A):
        if a == -1:
            continue
        if a < cur[j]:
            # 大きい要素から順に、まだ作っていない大きい要素を作っていく
            nxt.append(a)
            A[i] = -1
            j += 1
            # この世代は作り終わった
            if j == len(cur):
                break
    else:
        # 子要素を作れない要素があった
        No()
        exit()
    nxt.sort(reverse=1)
    cur = nxt[:]
Yes()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort(reverse=1)
cur = [A[0]]
# 作成済を-1とする
A[0] = -1

for _ in range(N):
    cur.sort(reverse=1)
    nxt = cur[:]
    j = 0
    for i, a in enumerate(A):
        if a == -1:
            continue
        if a < cur[j]:
            # 大きい要素から順に、まだ作っていない大きい要素を作っていく
            nxt.append(a)
            A[i] = -1
            j += 1
            # この世代は作り終わった
            if j == len(cur):
                break
    else:
        # 子要素を作れない要素があった
        No()
        exit()
    cur = nxt[:]
Yes()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import heapq as hp
from collections import Counter


def main():

    N = int(input())
    A = list(map(int, input().split()))
    graph = [[] for _ in range(1<<N)]

    for l in range(N):
        for n in range(1<<l):
            graph[n].append(n+(1<<l))

    C = Counter(A)
    Keys = sorted(C.keys(), reverse=True)
    
    q = [(-len(graph[0]), 0)]
    for key in Keys:
        num = C[key]
        if num > len(q):
            return False
        use = []
        for _ in range(num):
            _, p = hp.heappop(q)
            use.append(p)
        for p in use:
            for np in graph[p]:
                hp.heappush(q, (-len(graph[np]), np))

    return True

if __name__ == "__main__":
    print("Yes" if main() else "No")