fork download
copy 
  1. import math
  2. from collections import deque
  3. from heapq import heapify,heappop,heappush
  4. import sys
  5.  
  6. def find(u, par):
  7.  
  8.     if par[u] != u:
  9.         par[u] = find(par[u], par)
  10.     return par[u]
  11.  
  12. def union(u, v, par, size):
  13.     u_root = find(u, par)
  14.     v_root = find(v, par)
  15.  
  16.     if u_root == v_root:
  17.         return 
  18.  
  19.  
  20.     if size[u_root] < size[v_root]:
  21.         par[u_root] = v_root
  22.         size[v_root] += size[u_root]
  23.     else:
  24.         par[v_root] = u_root
  25.         size[u_root] += size[v_root]
  26.  
  27. def ip():
  28.     return map(int,input().split())
  29.  
  30.  
  31.  
  32. res=[]
  33. T=1
  34. T=int(input())
  35. for __ in range(T):
  36.     s=str(input())
  37.     t=int(input())
  38.     pq=[]
  39.     heapify(pq)
  40.     n=len(s)
  41.     if n==1:
  42.         res.append(s[0])
  43.         continue
  44.     for i in range(n-1):
  45.         if s[i]>s[i+1]:
  46.             heappush(pq,i)
  47.     l=[i-1 for i in range(n)]
  48.     r=[i+1 for i in range(n)]
  49.     d=[False for _ in range(n)]
  50.     curr=n
  51.     ct=0
  52.     fg=False
  53.     while pq:
  54.         if ct+curr>=t:
  55.             rem=t-ct
  56.             c=0
  57.             for i in range(n):
  58.                 if not d[i]:
  59.                     c+=1
  60.                 if c==rem:
  61.                     res.append(s[i])
  62.                     fg=True
  63.                     break
  64.  
  65.             break
  66.  
  67.         i=heappop(pq)
  68.         d[i]=True
  69.         # print(i)
  70.         # print(pq)
  71.         # print(l)
  72.         # print(r)
  73.         if i+1<n:
  74.             l[r[i]]=l[i]
  75.         if i-1>=0:
  76.             r[l[i]]=r[i]
  77.         if 0<=l[i]<n and 0<=r[i]<n:
  78.             if s[l[i]]>s[r[i]]:
  79.                 heappush(pq,l[i])
  80.  
  81.         ct+=curr
  82.         curr-=1
  83.         # print("after")
  84.         # print(pq)
  85.         # print(l)
  86.         # print(r)
  87.  
  88.     j=n-1
  89.     if fg:
  90.         continue
  91.     while True:
  92.  
  93.         if ct+curr>=t:
  94.             rem=t-ct
  95.             c=0
  96.             for i in range(n):
  97.                 if not d[i]:
  98.                     c+=1
  99.                 if c==rem:
  100.                     res.append(s[i])
  101.                     fg=True
  102.                     break
  103.             break  
  104.  
  105.         while j>=0 and d[i]:
  106.             j-=1
  107.         d[j]=True
  108.         ct+=curr
  109.         curr-=1
  110.  
  111.  
  112. print("".join(res))
  113.  
  114.  
  115.  
Success #stdin #stdout 0.07s 14164KB
comments (?)
stdin
copy 
3
cab
6
abcd
9
x
1
stdout
copy 
abx
https://ideone.com/6DsFfo
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!