Shurikens (Codeforces 1434B)
Tags: Greedy, data structures

Tenten runs a weapon shop for ninjas. Today she is willing to sell $$$n$$$ shurikens which cost $$$1$$$, $$$2$$$, ..., $$$n$$$ ryo (local currency). During a day, Tenten will place the shurikens onto the showcase, which is empty at the beginning of the day. Her job is fairly simple: sometimes Tenten places another shuriken (from the available shurikens) on the showcase, and sometimes a ninja comes in and buys a shuriken from the showcase. Since ninjas are thrifty, they always buy the cheapest shuriken from the showcase.Tenten keeps a record for all events, and she ends up with a list of the following types of records:  + means that she placed another shuriken on the showcase;  - x means that the shuriken of price $$$x$$$ was bought. Today was a lucky day, and all shurikens were bought. Now Tenten wonders if her list is consistent, and what could be a possible order of placing the shurikens on the showcase. Help her to find this out!

Input: The first line contains the only integer $$$n$$$ ($$$1\leq n\leq 10^5$$$) standing for the number of shurikens. The following $$$2n$$$ lines describe the events in the format described above. It's guaranteed that there are exactly $$$n$$$ events of the first type, and each price from $$$1$$$ to $$$n$$$ occurs exactly once in the events of the second type.

Output: If the list is consistent, print "YES". Otherwise (that is, if the list is contradictory and there is no valid order of shurikens placement), print "NO".In the first case the second line must contain $$$n$$$ space-separated integers denoting the prices of shurikens in order they were placed. If there are multiple answers, print any.

Note: In the first example Tenten first placed shurikens with prices $$$4$$$ and $$$2$$$. After this a customer came in and bought the cheapest shuriken which costed $$$2$$$. Next, Tenten added a shuriken with price $$$3$$$ on the showcase to the already placed $$$4$$$-ryo. Then a new customer bought this $$$3$$$-ryo shuriken. After this she added a $$$1$$$-ryo shuriken. Finally, the last two customers bought shurikens $$$1$$$ and $$$4$$$, respectively. Note that the order $$$[2, 4, 3, 1]$$$ is also valid.In the second example the first customer bought a shuriken before anything was placed, which is clearly impossible.In the third example Tenten put all her shurikens onto the showcase, after which a customer came in and bought a shuriken with price $$$2$$$. This is impossible since the shuriken was not the cheapest, we know that the $$$1$$$-ryo shuriken was also there.

Sample Inputs:
4
+
+
- 2
+
- 3
+
- 1
- 4

1
- 1
+

3
+
+
+
- 2
- 1
- 3

Sample Outputs:
YES
4 2 3 1

NO

NO

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
from heapq import *
n = II()
hp = []
tas = [SI().split() for _ in range(2 * n)]
ans = []
for ta in tas[::-1]:
    if ta[0] == '-':
        a = int(ta[1])
        heappush(hp, a)
    else:
        if not hp:
            print('NO')
            exit()
        a = heappop(hp)
        ans.append(a)
ans = ans[::-1]

def check():
    case = []
    i = 0
    for ta in tas:
        if ta[0] == '-':
            if not case:
                return False
            a = heappop(case)
            if a != int(ta[1]):
                return False
        else:
            heappush(case, ans[i])
            i += 1
    return True
if check():
    print('YES')
    print(*ans)
else:
    print('NO')

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
n = N()
res = [0] * (n + 2)
d = []
now = 0
flag = True
for _ in range(2 * n):
    s = input().strip()
    if s == '+':
        d.append(now)
        now += 1
    else:
        v = int(s[2:])
        if not d:
            flag = False
            break
        t = d.pop()
        if v < res[t + 1]:
            flag = False
            break
        res[t] = v
if not flag:
    print('NO')
else:
    print('YES')
    print_list(res[:n])

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
data = [line.strip() for line in sys.stdin.readlines()]
n = int(data[0])
res = [0] * (n + 2)
d = []
now = 0
flag = True
for i in range(1, 2 * n + 1):
    if data[i] == '+':
        d.append(now)
        now += 1
    else:
        v = int(data[i][2:])
        if not d:
            flag = False
            break
        t = d.pop()
        if v < res[t + 1]:
            flag = False
            break
        res[t] = v
if not flag:
    print('NO')
else:
    print('YES')
    print_list(res[:n])