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:
def main():
    INF = float("inf")

    N, *S = map(int, open(0).read().split())
    M = len(S)

    S.sort(reverse=True)

    Q = [S[0]]
    S[0] = INF
    for _ in range(N):
        Q.sort()
        T = Q[:]

        cur = 1
        while Q:
            p = Q.pop()
            while S[cur] >= p:
                cur += 1
                if cur == M:
                    print("No")
                    exit()
            T.append(S[cur])
            S[cur] = INF

        Q = T

    print("Yes")

main()

Submission status: Accepted

Solution code:
INF = float("inf")

N, *S = map(int, open(0).read().split())
M = len(S)

S.sort(reverse=True)

Q = [S[0]]
S[0] = INF
for _ in range(N):
    Q.sort()
    T = Q[:]

    cur = 1
    while Q:
        p = Q.pop()
        while S[cur] >= p:
            cur += 1
            if cur == M:
                print("No")
                exit()
        T.append(S[cur])
        S[cur] = INF

    Q = T

print("Yes")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = LI()
    b = list(set([i for i in s]))
    b.sort()
    f = {i:bisect.bisect_left(b,i) for i in s}
    s = [f[i] for i in s]
    m = max(s)
    d = [0]*(m+1)
    for i in s:
        d[i] += 1
    if d[m] > 1:
        print("No")
        return
    ans = defaultdict(lambda : 0)
    ans[m] = 1
    k = 2
    for i in range(n):
        na = defaultdict(lambda : 0)
        su = 0
        for j in range(k):
            l = m-j
            if l < 0:
                break
            na[l] = ans[l]
            p = d[l]-ans[l]
            if p > 0:
                if su < p:
                    na[l] += su
                    su = 0
                else:
                    na[l] = d[l]
                    su -= p
            su += ans[l]
            ans[l] = na[l]
        k <<= 1
    for i in s:
        if d[i] != ans[i]:
            print("No")
            return
    print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

N=int(input())
S=list(map(int,input().split()))
S.sort(reverse=True)
flag=[0]*2**N
flag[0]=1
for _ in range(N):
    h=flag[:]
    child=1
    for parent in range(2**N):
        if flag[parent]==0:
            continue
        while child<2**N:
            if flag[child]==0 and S[parent]>S[child]:
                h[child]=1
                child+=1
                break
            child+=1
    flag=h
for i in flag:
    if i==0:
        print("No")
        break
else:
    print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
N = int(input())
S = list(map(int,input().split()))
d = defaultdict(lambda:0)
for s in S:
    d[s] += 1
S = []
for s in d:
    S.append([s,d[s]])
S.sort(reverse=True)
S = [s[1] for s in S]
c = [-N]
possible = True
for s in S:
    if len(c)<s:
        possible = False
        break
    l = []
    for k in range(s):
        i = -heapq.heappop(c)
        l.append(i)
    for i in l:
        for j in range(i):
            heapq.heappush(c,-j)
if possible:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解答]
最初に生成⇒最大のスライム
2回目以降⇒できるだけ大きい値のスライムを先に生成したい
         ⇒生成できるスライムの中で最大のものを常に選択(貪欲)
         ⇒それをn回繰り返す
降順にソートして前から取ると速い(昇順,後ろからでも)
"""
n = I()
s = LI()
s.sort(reverse=True)
use = [s[0]]
rest = s[1:]
for _ in range(n):
    new_use = []
    que = deque(rest)
    for i in use:
        rest_tmp = []
        while que:
            x = que.popleft()
            if i > x:
                new_use.append(x)
                break
            else:
                rest_tmp.append(x)
        que += rest_tmp
    use += new_use
    use.sort(reverse=True)
    rest = list(que)
    rest.sort(reverse=True)
if len(use) == 2**n:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()
s.sort(reverse=True)
use = [s[0]]
rest = s[1:]
for _ in range(n):
    new_use = []
    que = deque(rest)
    for i in use:
        rest_tmp = []
        while que:
            x = que.popleft()
            if i > x:
                new_use.append(x)
                break
            else:
                rest_tmp.append(x)
        que += rest_tmp
    use += new_use
    use.sort(reverse=True)
    rest = list(que)
    rest.sort(reverse=True)
if len(use) == 2**n:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
import heapq

N = int(input())

S = list(map(int,input().split()))

dic = {}
lis = []

rem = 1
pl = 0
loop = N
flag = True

for i in range(2 ** N):

    if S[i] not in dic:
        dic[S[i]] = 1
        lis.append(S[i])

    else:
        dic[S[i]] += 1

lis.sort()
lis.reverse()

#print (lis,dic)

q = []

for i in lis:

    if len(q) == 0:
        if dic[i] != 1:
            print ("No")
            sys.exit()
        q = [-N]
        continue

    plq = []
    #print (q)
    
    for j in range(dic[i]):

        if len(q) == 0:
            print ("No")
            sys.exit()
            
        maxnum = -1 * heapq.heappop(q)
        plq.append(maxnum - 1)

        if maxnum > 1:
            heapq.heappush(q,-1 * (maxnum - 1))

        #print (q,plq)

    for j in plq:
        if j > 0:
            heapq.heappush(q,-1 * j)

    #print (i,q)


print ("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n**3)
    return

#B
def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return

#C
def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return

#D
def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
# ↑
# これは嘘
# BITを使え
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x < self.size:
            self.bit[x] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        ok = self.size
        ng = 0
        while abs(ok - ng) != 1:
            mid = (ok + ng)//2
            if self.sum(mid) >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def __len__(self):
        return self.size

def E():
    n = II()
    a = LI()
    dic = defaultdict(int)
    for i, ai in enumerate(a):
        dic[ai] = i+1
    bit = BinaryIndexedTree(n+1)
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        c = dic[i]
        L = bit.sum(c)
        bit.add(c,1)
        R = n-i-L 
        a = bit.search(L-1) if L >= 2 else 0
        b = bit.search(L) if L >= 1 else 0
        d = bit.search(L+2) if R >= 1 else n+1
        e = bit.search(L+3) if R >= 2 else n+1
        tmp = 0
        if b != 0:
            tmp += (b-a) * (d-c)
        if d != 0:
            tmp += (e-d) * (c-b)
        ans += i * tmp

    print(ans)
    return

#F
def F():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y: return
        if x > y: y, x = x, y
        par[x] = y
        return
    n = II()
    s = LI()
    s.sort(reverse=True)
    x = list(sorted(set(s)))[::-1]
    d = defaultdict(int)
    di = defaultdict(int)
    for i, xi in enumerate(x):
        d[xi] = i
    ma = i + 1
    num = [0] * (ma)
    par = [i for i in range(ma)]
    for si in s:
        num[d[si]] += 1
    l = [0]
    num[0] -= 1
    for _ in range(n):
        tmp = l[::1]
        for li in l:
            if root(li) + 1 < ma and num[root(li) + 1]:
                num[root(li)+1] -= 1
                tmp.append(root(li)+1)
            else:
                i = 0
                x = root(li)
                while root(x + i) + 1 < ma and (not num[root(x + i) + 1]):
                    i += 1
                unite(li, x + i)
                if root(li)+1 >= ma:
                    print("No")
                    return
                tmp.append(root(li)+1)
                num[root(li)+1] -= 1
        l = tmp[::1]
    print("Yes")
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Accepted

Solution code:
n = int(input())
s = [list(map(int, input().split()))]

s[0].sort(reverse=True)

t = [s[0].pop(0)]
s.append([0 for _ in range(2 ** n - 1)])
a = 0
b = 1
p = 1
q = 2 ** n - 1
for _ in range(n):
    #print(s)
    j = 0
    k = 0
    for i in range(p):
        if j >= q:
            print('No')
            exit()
        #print(i, t, s)
        while t[i] <= s[a][j]:
            s[b][k] = s[a][j]
            j += 1
            k += 1
            if j >= q:
                print('No')
                exit()
        t.append(s[a][j])
        j += 1
    t.sort(reverse=True)

    #print(i, j, q)
    while j < q:
        s[b][k] = s[a][j]
        k += 1
        j += 1
    a, b = b, a
    #print(s)
    q -= p
    p *= 2
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
S = list(map(int,input().split()))
S.sort()

used = [S.pop()]
for _ in range(N):
 
    l, r = 0, len(used)
    reuse = deque()
    for i in range(len(S)):
        v = S.pop()
        if v < used[l]:
            used.append(v)
            l += 1
        else:
            reuse.appendleft(v)
        if l == r:
            break
    else:
        print('No')
        break
    S.extend(reuse)
    used.sort(reverse=True)
else:
    print('Yes')

Submission status: Accepted

Solution code:
from random import random


class TreapNode():
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent = None
        self.right = None
        self.left = None
 
        
class Treap():
    def __init__(self, is_multiset=False):
        self.root = None
        self.is_multiset = is_multiset
 
    def search(self, val: int) -> bool:
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False 
 
    def insert(self, val: int):
        if self.root is None:
            self.root = TreapNode(val)
            return
 
        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
                if 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 
       
    def delete(self, val: int):
        if self.root is None:
            return
 
        ptr = self.root         
        while True: 
            if ptr is None:
                return
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
 
        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      
 
    def search_min(self, ptr):
        while True:
            if ptr.left is None:
                return ptr
            ptr = ptr.left
        return ptr
 
    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_less(self, val):
        if val == None:
            return None
        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


n = int(input())
a = list(map(int, input().split()))

tp = Treap(True)
max_a = max(a)

for i in range(2**n):
    tp.insert(a[i])

tp.delete(max_a)

slime = [max_a]
for _ in range(n):
    li = []
    for val in slime:
        tmp = tp.search_less(val)
        if tmp is None:
            print("No")
            exit()
        tp.delete(tmp)
        li.append(tmp)
    slime = slime + li
print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007




n =  I()
final_slime = sorted(LI(), reverse=True)
now_slime = [final_slime[0]]
made_or_not = [0] * (2 ** n)
made_or_not[0] = 1
for i in range(n):
    k = 0
    for j in range(len(now_slime)):
        flag = 1
        while flag:
            if k == 2 ** n:
                print('No')
                exit(0)
            if made_or_not[k] == 0 and now_slime[j] - 1 >= final_slime[k]:
                now_slime += [final_slime[k]]
                made_or_not[k] = 1
                flag = 0
            k += 1
    now_slime.sort(reverse=True)
print('Yes')

Submission status: Accepted

Solution code:
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

    # i+1番目からR番目まで足すとt以上となるような最小のRを返す
    def bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    # L番目からi-1番目まで足すとt以上となるような最小のLを返す
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


N = int(input())
S_raw = list(map(int, input().split()))

S_raw.sort()
k = 1
S = [1]
for i in range(1, len(S_raw)):
    if S_raw[i] != S_raw[i-1]:
        k += 1
    S.append(k)

bit = Bit(S[-1] + 1)
for s in S:
    bit.add(s, 1)
slimes = [S[-1]]
for t in range(N):
    slimes_new = []
    for sl in slimes:
        sl_new = bit.bisect_minus(sl, 1)
        if sl_new == 0:
            print('No')
            exit()
        slimes_new.append(sl_new)
        bit.add(sl_new, -1)
    slimes.extend(slimes_new)

print('Yes')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list(map(int, input().split()))
    INF = float('inf')
    n = 2 ** N + 1

    S.sort()

    parents = [S[-1]]
    S[-1] = INF

    for _ in range(N):
        checking = 2
        parents.sort(reverse=True)
        for i in parents[:]:
            while True:
                if S[-checking] < i:
                    parents.append(S[-checking])
                    S[-checking] = INF
                    break
                else:
                    checking += 1
                if checking == n:
                    print('No')
                    exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list(map(int, input().split()))
    INF = float('inf')
    n = 2 ** N + 1

    S.sort()

    parents = [S[-1]]
    S[-1] = INF

    for _ in range(N):
        checking = 2
        parents.sort()
        tmp = parents[::-1]
        for i in tmp:
            while True:
                if S[-checking] < i:
                    parents.append(S[-checking])
                    S[-checking] = INF
                    break
                else:
                    checking += 1
                if checking == n:
                    print('No')
                    exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list(map(int, input().split()))
    INF = float('inf')

    S.sort()

    parents = [S[-1]]
    S[-1] = INF

    for _ in range(N):
        checking = 2
        parents.sort()
        tmp = parents[::-1]
        for i in tmp:
            while True:
                if S[-checking] < i:
                    parents.append(S[-checking])
                    S[-checking] = INF
                    break
                else:
                    checking += 1
                if checking == 2 ** N + 1:
                    print('No')
                    exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list(map(int, input().split()))
    INF = float('inf')

    S.sort()

    parents = [S[-1]]
    S[-1] = INF

    for _ in range(N):
        checking = 2
        parents.sort(reverse=True)
        for i in parents[:]:
            while True:
                if S[-checking] < i:
                    parents.append(S[-checking])
                    S[-checking] = INF
                    break
                else:
                    checking += 1
                if checking == 2 ** N + 1:
                    print('No')
                    exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
INF = 10 ** 10

S.sort()

parents = [S[-1]]
S[-1] = INF
from_here = 1

for _ in range(N):
    checking = from_here
    first = True
    parents.sort(reverse=True)
    for i in parents[:]:
        while True:
            if S[-checking] < i and first:
                parents.append(S[-checking])
                S[-checking] = INF
                from_here = checking + 1
                break
            elif S[-checking] < i:
                parents.append(S[-checking])
                S[-checking] = INF
                break
            else:
                checking += 1
                first = False
            if checking == 2 ** N + 1:
                print('No')
                exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
INF = float('inf')

S.sort()

parents = [S[-1]]
S[-1] = INF
checked = 1

for _ in range(N):
    checking = checked
    first = True
    parents.sort(reverse=True)
    for i in parents[:]:
        while True:
            if S[-checking] < i and first:
                parents.append(S[-checking])
                S[-checking] = INF
                checked = checking + 1
                break
            elif S[-checking] < i:
                parents.append(S[-checking])
                S[-checking] = INF
                break
            else:
                checking += 1
                first = False
            if checking == 2 ** N + 1:
                print('No')
                exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
INF = float('inf')

S.sort()

parents = [S[-1]]
S[-1] = INF

for _ in range(N):
    checking = 2
    parents.sort(reverse=True)
    for i in parents[:]:
        while True:
            if S[-checking] < i:
                parents.append(S[-checking])
                S[-checking] = INF
                break
            else:
                checking += 1
            if checking == 2 ** N + 1:
                print('No')
                exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
n = int(input())
s = list(map(int, sys.stdin.readline().split()))

s.sort()#popするのでreverseしない
#print(s)
P = [s[-1]]
P_next = []

Rem = s[:-1]
Rem_next = []
for _ in range(n):
    while P:
        p = P.pop()
        P_next.append(p)
        while Rem:
            r = Rem.pop()
            if p>r:
                P_next.append(r)
                break
            Rem_next.append(r)
        """
        while p == Rem[-1]:
            r = Rem.pop()
            Rem_next.append(r)
        if Rem:
            P_next.append(Rem.pop())
        """
    P = P_next
    P_next = []
    Rem += Rem_next
    Rem_next = []
    #不自然な置き換えに見えるがlistからremoveするよりはマシか
    P.sort()
    Rem.sort()
if len(P) == 2**n:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: return self.hq[0].val
        else: return self.hq[0]

N = I()
S = III()

S.sort()
a = [Heapq([],True) for _ in range(N+1)]
count = [0]*(N+1)

s = S.pop()
a[N].push(s)
count[N] = 1

while S:
    flag = False
    temp = S.pop()
    for i in range(1,N+1)[::-1]:
        if count[i]:
            if temp<a[i].top():
                x = a[i].pop()
                count[i] -= 1
                a[i-1].push(x)
                a[i-1].push(temp)
                count[i-1] += 2
                flag = True
                break
    if not flag:
        print('No')
        exit()

print('Yes')