結果

問題 No.2804 Fixer And Ratism
ユーザー ArleenArleen
提出日時 2024-07-12 22:02:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 15,879 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 82,860 KB
実行使用メモリ 108,012 KB
最終ジャッジ日時 2024-07-12 22:02:48
合計ジャッジ時間 8,387 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
65,024 KB
testcase_01 AC 73 ms
65,024 KB
testcase_02 AC 61 ms
64,768 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 103 ms
78,336 KB
testcase_10 WA -
testcase_11 AC 235 ms
95,512 KB
testcase_12 WA -
testcase_13 AC 120 ms
80,868 KB
testcase_14 AC 184 ms
90,788 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 132 ms
82,588 KB
testcase_18 WA -
testcase_19 AC 92 ms
77,696 KB
testcase_20 WA -
testcase_21 AC 274 ms
99,092 KB
testcase_22 WA -
testcase_23 AC 321 ms
106,880 KB
testcase_24 WA -
testcase_25 AC 323 ms
107,136 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 311 ms
107,476 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 317 ms
107,008 KB
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import itertools
import time
import heapq
from math import radians, sin, cos, tan, sqrt, comb, pow
from math import log, log2, log10, exp
from collections import deque
from operator import mul
from functools import reduce, cmp_to_key
from random import randint, randrange
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().replace('\n','')
#sys.setrecursionlimit(300000)
md1 = 998244353
md2 = 10 ** 9 + 7
inf = 2 ** 31 + 1
primeset = set()
primelist = []
fenwick = []

# 入力ツール
# 1行の入力を整数のリストとして受け取る
def intlist():
    return list(map(int, input().split()))

# 1行から複数個の整数を受け取る
def getints():
    return tuple(map(int, input().split()))

# n行の入力を文字列のリストとして受け取る
def strtable(n):
    lst = []
    for i in range(0, n):
        lst.append(input())
    return lst

# n行の入力を整数のリストとして受け取る
def inttable(n):
    return list(map(int, strtable(n)))

# 整数のリストをn個受け取る
def intlisttable(n):
    lst = []
    for i in range(0, n):
        lst.append(intlist())
    return lst

# n個のクエリを先頭だけ整数、他を文字列のリストとして受け取る
def getquery(n):
    lst = []
    for i in range(0, n):
        query = list(input().split())
        qr = int(query[0])
        lst.append((qr, query[1:]))
    return lst

#==========
# 生成ツール
# H行W列のリスト生成
def twodimlist(h, w, init): # initの値で初期化
    lst1 = []
    for i in range(0, h):
        lst2 = []
        for j in range(0, w):
            lst2.append(init)
        lst1.append(lst2)
    return lst1

# 素数テーブルをsetとして生成
def genprimeset(n): #n以下の素数を列挙
    global primeset, primelist
    left = list(primeset)
    right = deque()
    start = 2
    if len(left) != 0:
        start = pt[-1] + 1
    for i in range(start, n+1):
        right.append(i)
    while len(right) != 0:
        flag = True
        now = right.popleft()
        for i in range(0, len(left)):
            if now < left[i] ** 2:
                break
            if now % left[i] == 0:
                flag = False
                break
        if flag:
            left.append(now)
    return set(left)

#==========
# 数え上げ
# 1次元数え上げ
def cntx(itr, x):
    cnt = 0
    for i in range(0, len(itr)):
        if itr[i] == x:
            cnt += 1
    return cnt

# 2次元数え上げ
def twodimcntx(itr, x):
    sm = 0
    for i in range(0, len(itr)):
        sm += cntx(itr[i], x)
    return sm

# 全要素数え上げ
def allcnt(itr):
    dct = {}
    for i in range(0, len(itr)):
        if itr[i] not in dct:
            dct[itr[i]] = 0
        dct[itr[i]] += 1
    return dct

# 2次元全要素数え上げ
def twodimallcnt(itr, x):
    dct = {}
    for i in range(0, len(itr)):
        for j in range(0, len(itr[i])):
            if itr[i][j] not in dct:
                dct[itr[i][j]] = 0
            dct[itr[i][j]] += 1
    return dct

#==========
# 計算ツール
# 最大公約数
def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if x % y == 0:
        return y
    return gcd(y, x%y)

# 最小公倍数
def lcm(x, y):
    g = gcd(x, y)
    return (x*y) // g

# フィボナッチ数列(0-indexで、第n項まで生成)
def genfib(n, m): # m == 0ならmodなし、m == 1ならmd1でmod, m == 2ならmd2でmod
    lst = [1, 1]
    if m == 0:
        for i in range(1, n):
            lst.append(lst[-2]+lst[-1])
    else:
        md = md1
        if m == 2:
            md = md2
        for i in range(1, n):
            lst.append((lst[-2]+lst[-1])%md)
    return lst

# 素数一覧の初期化
def primeinit(x):
    global primeset, primelist
    primeset = genprimeset(x)
    primelist = list(primeset)
    return

# 素数判定
def isitprime(x):
    if x < 2:
        return False
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    if x in primeset:
        return True
    for i in range(0, len(primelist)):
        if x % primelist[i] == 0:
            return False
    return True

# 素因数分解
def factorize(x):
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    dct = {}
    now = x
    for i in range(0, len(primelist)):
        if x < primelist[i] ** 2:
            break
        while now % primelist[i] == 0:
            if primelist[i] not in dct:
                dct[primelist[i]] = 0
            dct[primelist[i]] += 1
            now //= primelist[i]
    if now != 1:
        dct[now] = 1
    return dct

# Coprime判定
def coprime(x, y):
    return gcd(x, y) == 1

# 約数列挙
def divisor(x):
    s = set()
    for i in range(1, x+1):
        if x < i ** 2:
            break
        if x % i == 0:
            s.add(i)
            s.add(x//i)
    lst = sorted(list(s))
    return lst

# 約数数え上げ
def countdivisor(x):
    fact = factorize(x)
    key = list(fact.keys())
    cnt = 1
    for i in range(0, len(key)):
        cnt *= fact[key[i]] + 1
    return cnt

# 大文字->小文字変換
def uppertolower(c):
    if 'A' <= c and c <= 'Z':
        return chr(ord(c)+32)
    return c

# 小文字->大文字変換
def lowertoupper(c):
    if 'a' <= c and c <= 'z':
        return chr(ord(c)-32)
    return c

# 大文字小文字相互変換
def upperlower(c):
    newc = uppertolower(c)
    if c == newc:
        newc = lowertoupper(c)
    return newc

# x以上の要素の個数
def xormore(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_left(lst, x)

# xより大きい要素の個数
def morethanx(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_right(lst, x)

# x以下の要素の個数
def xorless(lst, x): # lstはソート済みにすること
    return bisect_right(lst, x)

# x未満の要素の個数
def lessthanx(lst, x): # lstはソート済みにすること
    return bisect_left(lst, x)

# 各桁の総和
def digitsum(x):
    nm = str(x)
    sm = 0
    for i in range(0, len(nm)):
        sm += int(nm[i])
    return sm

# bitカウント(64bitまで)
def popcount(x):
    now = x
    now = now - ((now >> 1) & 0x5555555555555555)
    now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333)
    now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f
    n = 8
    for i in range(0, 3):
        now += (now >> n)
        n *= 2
    return now & 0x0000007f

# xの累乗リスト(0乗からn乗まで)
def powtable(x, n, m): # modなしの場合はm = 0に設定する
    md = m
    if m == 1: # m == 1ならmd1でmod
        md = md1
    elif m == 2: # m == 2ならmd2でmod
        md = md2
    
    lst = [1]
    for i in range(0, n):
        if md == 0:
            lst.append(lst[-1]*x)
        else:
            lst.append((lst[-1]*x)%md)
    return lst

# ==========
# グラフツール
# グラフの初期化
def defgraph(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = set()
    return graph

# 重み付きグラフの初期化
def defgraphw(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = {}
    return graph

# 無向グラフ生成
def undirgraph(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
        graph[v].add(u)
    return graph

# 重み付き無向グラフ生成
def undirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
        graph[v][u] = wdict[elist[i]]
    return graph

# 有向グラフ生成
def dirgraph(vlist, elist): # 辺の形式は(u, v)で、向きはu -> v
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
    return graph

# 重み付き有向グラフ生成
def dirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
    return graph

# 重み無し最短ステップ
def shortest(vlist, elist, graph, st, gl):
    if st not in graph or gl not in graph:
        return -1
    yet = set(vlist)
    q = deque()
    q.append((st, 0))
    yet.discard(st)
    while len(q) != 0:
        now = q.popleft()
        v = now[0]
        s = now[1]
        if v == gl:
            return s
        lst = list(graph[v])
        for i in range(0, len(lst)):
            nxtv = lst[i]
            if nxtv in yet:
                yet.discard(nxtv)
                q.append((nxtv, s+1))
    return -1

# ダイクストラ
def dijkstra(vlist, elist, graph, st):
    cur = {}
    for i in range(0, len(vlist)):
        cur[vlist[i]] = inf
    cur[st] = 0
    dist = {}
    h = []
    heapq.heapify(h)
    heapq.heappush(h, (0, st))
    
    while len(h) != 0:
        now = heapq.heappop(h)
        d = now[0]
        v = now[1]
        if v in dist:
            continue
        dist[v] = d
        lst = list(graph[v].keys())
        for i in range(0, len(lst)):
            nxt = lst[i]
            if nxt not in dist:
                nxtd = dist[v] + graph[v][nxt]
                cur[nxt] = min(cur[nxt], nxtd)
                if cur[nxt] == nxtd:
                    heapq.heappush(h, (nxtd, nxt))
    return dist

# Union-Find生成
def genunionfind(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    root = {}
    vcnt = {}
    flag = False
    for i in range(0, len(vlist)):
        root[vlist[i]] = vlist[i]
        vcnt[vlist[i]] = 1
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        ur = root[u]
        vr = root[v]
        if ur == vr:
            flag = True
        else:
            H = ur
            L = vr
            if vcnt[ur] < vcnt[vr]:
                H = vr
                L = ur
            graph[H].add(L)
            vcnt[H] += vcnt[L]
            q = deque()
            q.append(L)
            while len(q) != 0:
                now = q.popleft()
                root[now] = H
                lst = list(graph[now])
                for j in range(0, len(lst)):
                    q.append(lst[j])
    return (graph, root, vcnt, flag) # (グラフ, 根, 頂点の数, ループ検出)の形式で返す

# ==========
# fenwick木
# fenwickを初期化
def initfenwick(n, init):
    global fenwick
    fenwick = []
    for i in range(0, n+1):
        fenwick.append(init)
    return

# idx番目までの和を求める
def fwsum(idx):
    sm = 0
    now = idx
    while now > 0:
        sm += fenwick[now]
        now -= -now & now
    return sm

# idx番目の値にxを足す
def fwadd(idx, x):
    global fenwick
    now = idx
    while now < len(fenwick):
        fenwick[now] += x
        now += -now & now
    return

# 転倒数
def inversion(A):
    global fenwick
    initfenwick(len(A), 0)
    sm = 0
    for i in range(0, len(A)):
        sm += i - fwsum(A[i])
        fwadd(A[i], 1)
    return sm

# ==========
# ハッシュ
Mset = set()
Mlist = []

# Mの候補の素数を生成
def initM():
    global Mset, Mlist
    a = 10 ** 9
    for i in range(-10000, 10001):
        if isitprime(a+i):
            Mset.add(a+i)
    Mlist = list(Mset)
    return

# Bの累乗を生成
def genB(b, m, n):
    lst = [1]
    for i in range(0, n):
        lst.append((lst[-1]*b)%m)
    return lst

# ハッシュテーブル生成
def genH(b, m, s):
    lst = [0]
    for i in range(0, len(s)):
        a = ord(s[i]) - ord('a') + 1
        lst.append((b*lst[-1]+a)%m)
    return lst

# 部分文字列のハッシュ値を求める
def Hval(Hlist, Blist, M, L, R):
    return (Hlist[R] - Blist[R-L+1]*Hlist[L-1]) % M

# ハッシュを複数生成
def multihash(s):
    global Mset, Mlist
    if len(Mlist) == 0:
        initM()
    bm = {}
    for i in range(0, 5):
        b = randint(9900, 11000)
        m = Mlist[randrange(0, len(Mlist))]
        while (b, m) in bm:
            b = randint(9900, 11000)
            m = Mlist[randrange(0, len(Mlist))]
        Blist = genB(b, m, len(s))
        Hlist = genH(b, m, s)
        bm[(b, m)] = (Blist, Hlist)
    return bm

# 指定したb, mでハッシュ生成
def multihashconst(s, bmkey):
    h = {}
    for i in range(0, 5):
        b = bmkey[i][0]
        m = bmkey[i][1]
        Blist = genB(b, m, len(s))
        Hlist = genH(b, m, s)
        h[(b, m)] = (Blist, Hlist)
    return h

# ==========
# 【問題要約】
# 競プロ部には100人の部員がおり、部室には10^9台のパソコンがある
# 時刻0の時点では、そのうちのN台のパソコンが使用可能である
# クエリがQ個与えられる
# i番目(where 1<=i<=Q)のクエリは、時刻iに起きた出来事を表し、
# それぞれ以下の形式のうちのいずれかが与えられる
#  * 1 s r: レートrの部員sが部室にくる
#  * 2 x: x台のパソコンが使用できなくなる
#  * 3 s x: 部室にいる部員sが、x個のパソコンを使用可能にする
# パソコンは以下のような順番で、現在使用可能なパソコンの台数に対し1人1台使う
#  * パソコンを1台でも使用可能にしたことがある人のうち、レートが高い順
#  * 上に当てはまる人全員が使ってもまだ使えるパソコンがある場合は、
#    上に当てはまらない人の中でレートが高い順
# 使用可能なパソコンの台数よりも現在部室にいる部員の人数の方が多くなった場合は
# 上の順番によってパソコンを使える部員を決め、使えない部員は帰る
# 一度帰った人が再度部室に来ることはない
# 帰った人の名前を、帰った時刻が早い人から順に1人1行ずつすべて出力せよ
# 同時に複数人が帰った場合は、同時に帰った人々の名前をレートが低い人から順に出力せよ
#
# 1 <= N <= 100
# 1 <= Q <= 100000
# 0 <= r <= 4000
# 1 <= x <= 10
# 1 <= |s| <= 100
# sは英小文字のみからなる
# s以外の入力はすべて整数
# 部員の名前は高々100種類
# 部員の名前とレートはそれぞれ相異なる
# 使用可能なパソコンの台数は常に1以上である
# クエリ1で与えられる部員はまだ部室に来ていない
# クエリ3で与えられる部員は部室にいる
#
# ==========
# コードはここから書く
N, Q = getints()
query = getquery(Q)

leave = []
fixed = []
fixset = set()
comer = []
avl = N
cnt = 0
for i in range(0, Q):
    qr = query[i][0]
    if qr == 1:
        s = query[i][1][0]
        r = int(query[i][1][1])
        heapq.heappush(comer, (r, s))
        cnt += 1
    elif qr == 2:
        x = int(query[i][1][0])
        avl -= x
    else:
        s = query[i][1][0]
        x = int(query[i][1][1])
        avl += x
        heapq.heappush(fixed, (r, s))
        fixset.add(s)
    
    lv = []
    if cnt > avl:
        while len(comer) != 0:
            if cnt == avl:
                break
            now = heapq.heappop(comer)
            nm = now[1]
            if nm not in fixset:
                lv.append(now)
                cnt -= 1
    if cnt > avl:
        while len(fixed) != 0:
            if cnt == avl:
                break
            now = heapq.heappop(fixed)
            lv.append(now)
            cnt -= 1
    lv.sort(key=lambda a: a[0])
    for j in range(0, len(lv)):
        leave.append(lv[j][1])

for i in range(0, len(leave)):
    print(leave[i])

0