結果
問題 | No.2868 Another String of yuusaan |
ユーザー | lif4635 |
提出日時 | 2025-01-20 21:40:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 9,081 bytes |
コンパイル時間 | 1,455 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 68,864 KB |
最終ジャッジ日時 | 2025-01-20 21:40:44 |
合計ジャッジ時間 | 4,347 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
# inputimport sysinput = sys.stdin.readlineII = lambda : int(input())MI = lambda : map(int, input().split())LI = lambda : list(map(int, input().split()))SI = lambda : input().rstrip()LLI = lambda n : [list(map(int, input().split())) for _ in range(n)]LSI = lambda n : [input().rstrip() for _ in range(n)]MI_1 = lambda : map(lambda x:int(x)-1, input().split())LI_1 = lambda : list(map(lambda x:int(x)-1, input().split()))def graph(n:int, m:int, dir:bool=False, index:int=-1):edge = [set() for i in range(n+1+index)]for _ in range(m):a,b = map(int, input().split())a += indexb += indexedge[a].add(b)if not dir:edge[b].add(a)return edgedef graph_w(n:int, m:int, dir:bool=False, index:int=-1):edge = [set() for i in range(n+1+index)]for _ in range(m):a,b,c = map(int, input().split())a += indexb += indexedge[a].add((b,c))if not dir:edge[b].add((a,c))return edgemod, inf = 998244353, 1001001001001001001ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97yes = lambda : print("Yes")no = lambda : print("No")yn = lambda flag : print("Yes" if flag else "No")def acc(a:list[int]):sa = [0]*(len(a)+1)for i in range(len(a)):sa[i+1] = a[i] + sa[i]return saprinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)alplow = "abcdefghijklmnopqrstuvwxyz"alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]# sys.setrecursionlimit(10**5)# sys.set_int_max_str_digits(0)# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.pyimport mathfrom bisect import bisect_left, bisect_rightfrom typing import Generic, Iterable, Iterator, TypeVarT = TypeVar('T')class SortedSet(Generic[T]):BUCKET_RATIO = 16SPLIT_RATIO = 24def __init__(self, a: Iterable[T] = []) -> None:"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"a = list(a)n = len(a)if any(a[i] > a[i + 1] for i in range(n - 1)):a.sort()if any(a[i] >= a[i + 1] for i in range(n - 1)):a, b = [], afor x in b:if not a or a[-1] != x:a.append(x)n = self.size = len(a)num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]def __iter__(self) -> Iterator[T]:for i in self.a:for j in i: yield jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __eq__(self, other) -> bool:return list(self) == list(other)def __len__(self) -> int:return self.sizedef __repr__(self) -> str:return "SortedSet" + str(self.a)def __str__(self) -> str:s = str(list(self))return "{" + s[1 : len(s) - 1] + "}"def _position(self, x: T) -> tuple[list[T], int, int]:"return the bucket, index of the bucket and position in which x should be. self must not be empty."for i, a in enumerate(self.a):if x <= a[-1]: breakreturn (a, i, bisect_left(a, x))def __contains__(self, x: T) -> bool:if self.size == 0: return Falsea, _, i = self._position(x)return i != len(a) and a[i] == xdef add(self, x: T) -> bool:"Add an element and return True if added. / O(√N)"if self.size == 0:self.a = [[x]]self.size = 1return Truea, b, i = self._position(x)if i != len(a) and a[i] == x: return Falsea.insert(i, x)self.size += 1if len(a) > len(self.a) * self.SPLIT_RATIO:mid = len(a) >> 1self.a[b:b+1] = [a[:mid], a[mid:]]return Truedef _pop(self, a: list[T], b: int, i: int) -> T:ans = a.pop(i)self.size -= 1if not a: del self.a[b]return ansdef discard(self, x: T) -> bool:"Remove an element and return True if removed. / O(√N)"if self.size == 0: return Falsea, b, i = self._position(x)if i == len(a) or a[i] != x: return Falseself._pop(a, b, i)return Truedef lt(self, x: T) -> T | None:"Find the largest element < x, or None if it doesn't exist."for a in reversed(self.a):if a[0] < x:return a[bisect_left(a, x) - 1]def le(self, x: T) -> T | None:"Find the largest element <= x, or None if it doesn't exist."for a in reversed(self.a):if a[0] <= x:return a[bisect_right(a, x) - 1]def gt(self, x: T) -> T | None:"Find the smallest element > x, or None if it doesn't exist."for a in self.a:if a[-1] > x:return a[bisect_right(a, x)]def ge(self, x: T) -> T | None:"Find the smallest element >= x, or None if it doesn't exist."for a in self.a:if a[-1] >= x:return a[bisect_left(a, x)]def __getitem__(self, i: int) -> T:"Return the i-th element."if i < 0:for a in reversed(self.a):i += len(a)if i >= 0: return a[i]else:for a in self.a:if i < len(a): return a[i]i -= len(a)raise IndexErrordef pop(self, i: int = -1) -> T:"Pop and return the i-th element."if i < 0:for b, a in enumerate(reversed(self.a)):i += len(a)if i >= 0: return self._pop(a, ~b, i)else:for b, a in enumerate(self.a):if i < len(a): return self._pop(a, b, i)i -= len(a)raise IndexErrordef index(self, x: T) -> int:"Count the number of elements < x."ans = 0for a in self.a:if a[-1] >= x:return ans + bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:"Count the number of elements <= x."ans = 0for a in self.a:if a[-1] > x:return ans + bisect_right(a, x)ans += len(a)return ansclass BIT:def __init__(self, n):self.n = nself.data = [0]*(n+1)def add(self, p, x):p += 1while p < self.n:self.data[p] += xp += p& -pdef sum0(self, r):s = 0while r > 0:s += self.data[r]r -= r& -rreturn sdef sum(self, l, r):return self.sum0(r) - self.sum0(l)def get(self, p):return self.sum0(p+1) - self.sum0(p)def __str__(self):return str([self.get(i) for i in range(self.n)])def inversion_cnt(lst:list) -> int:"""i > j && a_i < a_j"""n = len(lst)maxlst = max(lst)if maxlst >= n+10:order = {x:i for i,x in enumerate(sorted(set(lst)))}lst = [order[x] for x in lst]ft = BIT(n+10)ans = [0]*nfor i in range(n):ans[i] = ft.sum(lst[i]+1,n)ft.add(lst[i], 1)return ansdef run_length_encode(s):encoded = []n = len(s)i = 0while i < n:current_char = s[i]count = 0while i < n and s[i] == current_char:count += 1i += 1encoded.append((current_char, count))return encodedn,k = MI()k -= 1if k <= n:print("y")exit()# level 25に帰着してもよいif n >= 25:k -= (n-25)n = 25# print((1<<51) - 1 > 10**15)def solve(n,k):if n == 1:return "yuusaan"[k]l = (1<<2*n-1) - 1 #level n-1のながさif k == 0:return "y"elif 1 <= k < l+1:return solve(n-1,k-1)elif l+1 <= k < 2*l+1:return solve(n-1,k-(l+1))elif 2*l+1 == k:return "s"elif 2*l+2 <= k < 3*l+2:return solve(n-1,k-(2*l+2))elif 3*l+2 <= k < 4*l+2:return solve(n-1,k-(3*l+2))elif 4*l+2 == k:return "n"else:assert Falseprint(solve(n,k))# yuu = "suusuus"# def calc(now):# res = []# for i in now:# if i == "u":# res.append(yuu)# else:# res.append(i)# return "".join(res)# now = yuu# for i in range(3):# now = calc(now)# print(*(c for i,c in run_length_encode(now)))