結果

問題 No.3036 Nauclhlt型文字列
ユーザー hidehic0
提出日時 2025-02-28 21:25:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 322 ms / 2,000 ms
コード長 22,536 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 88,848 KB
最終ジャッジ日時 2025-02-28 21:26:00
合計ジャッジ時間 2,417 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

r"""
______________________
< it's hidehico's code >
----------------------
\
\
.--.
|o_o |
|:_/ |
// \ \
(| | )
/'\_ _/`\
\___)=(___/
"""
# 便
#
import bisect
import copy
import heapq
import math
import sys
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from math import gcd, lcm, pi
from operator import itemgetter
from typing import Any, List, Tuple
# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.dsu import DSU
# cortedcontainers使 wandbox
# from sortedcontainers import SortedDict, SortedSet, SortedList
# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
sys.setrecursionlimit(5 * 10**5)
from typing import List
#
def is_prime(n: int) -> int:
"""
使
n2^64
"""
if n == 1:
return False
def f(a, t, n):
x = pow(a, t, n)
nt = n - 1
while t != nt and x != 1 and x != nt:
x = pow(x, 2, n)
t <<= 1
return t & 1 or x == nt
if n == 2:
return True
elif n % 2 == 0:
return False
d = n - 1
d >>= 1
while d & 1 == 0:
d >>= 1
checklist = (
[2, 7, 61] if 2**32 > n else [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
)
for i in checklist:
if i >= n:
break
if not f(i, d, n):
return False
return True
def eratosthenes(n: int) -> List[int]:
"""
n
O(n log log n)
"""
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
i = 2
while i**2 <= n:
if primes[i]:
for k in range(i * 2, n + 1, i):
primes[k] = False
i += 1
return [i for i, p in enumerate(primes) if p]
def calc_divisors(n: int):
"""
N
√N
"""
result = []
for i in range(1, n + 1):
if i * i > n:
break
if n % i != 0:
continue
result.append(i)
if n // i != i:
result.append(n // i)
return sorted(result)
def factorization(n: int) -> List[List[int]]:
"""
n
√N()
√N
"""
result = []
tmp = n
for i in range(2, int(-(-(n**0.5) // 1)) + 1):
if tmp % i == 0:
cnt = 0
while tmp % i == 0:
cnt += 1
tmp //= i
result.append([i, cnt])
if tmp != 1:
result.append([tmp, 1])
if result == []:
result.append([n, 1])
return result
def factorization_plural(L: List[int]) -> List[List[List[int]]]:
"""
O(N * (√max(L) log log √max(L)))
"""
res = []
primes = eratosthenes(int(max(L) ** 0.5) + 20)
def solve(n):
t = []
for p in primes:
if n % p == 0:
cnt = 0
while n % p == 0:
cnt += 1
n //= p
t.append([p, cnt])
if n != 1:
t.append([n, 1])
if t == []:
t.append([n, 1])
return t
for n in L:
res.append(solve(n))
return res
def simple_sigma(n: int) -> int:
"""
1n
"""
return (n * (n + 1)) // 2
def comb(n: int, r: int, mod: int | None = None) -> int:
"""
modmod
"""
a = 1
for i in range(n - r + 1, n + 1):
a *= i
if mod:
a %= mod
b = 1
for i in range(1, r + 1):
b *= i
if mod:
b %= mod
if mod:
return a * pow(b, -1, mod) % mod
else:
return a * b
#
from typing import Any, List
def create_array1(n: int, default: Any = 0) -> List[Any]:
"""
1
"""
return [default] * n
def create_array2(a: int, b: int, default: Any = 0) -> List[List[Any]]:
"""
2
"""
return [[default] * b for _ in [0] * a]
def create_array3(a: int, b: int, c: int, default: Any = 0) -> List[List[List[Any]]]:
"""
3
"""
return [[[default] * c for _ in [0] * b] for _ in [0] * a]
from typing import Callable
def binary_search(
fn: Callable[[int], bool], right: int = 0, left: int = -1, return_left: bool = True
) -> int:
"""
left
def check(mid:int):
if A[mid] > x:
return True
else:
return False
mid
"""
while right - left > 1:
mid = (left + right) // 2
if fn(mid):
left = mid
else:
right = mid
return left if return_left else right
def mod_add(a: int, b: int, mod: int):
"""
mod
O(1)
"""
return (a + b) % mod
def mod_sub(a: int, b: int, mod: int):
"""
mod
O(1)
"""
return (a - b) % mod
def mod_mul(a: int, b: int, mod: int):
"""
mod
O(1)
"""
return (a * b) % mod
def mod_div(a: int, b: int, mod: int):
"""
mod
使
O(log mod)
"""
return (a * pow(b, mod - 2, mod)) % mod
class ModInt:
def __init__(self, x: int, mod: int = 998244353) -> None:
self.x = x % mod
self.mod = mod
def val(self):
return self.x
def rhs(self, rhs) -> int:
return rhs.x if isinstance(rhs, ModInt) else rhs
def __add__(self, rhs) -> int:
return mod_add(self.x, self.rhs(rhs), self.mod)
def __iadd__(self, rhs) -> "ModInt":
self.x = self.__add__(rhs)
return self
def __sub__(self, rhs) -> int:
return mod_sub(self.x, self.rhs(rhs), self.mod)
def __isub__(self, rhs) -> "ModInt":
self.x = self.__sub__(rhs)
return self
def __mul__(self, rhs):
return mod_mul(self.x, self.rhs(rhs), self.mod)
def __imul__(self, rhs):
self.x = self.__mul__(rhs)
return self
def __truediv__(self, rhs):
return mod_div(self.x, self.rhs(rhs), self.mod)
def __itruediv__(self, rhs):
self.x = self.__truediv__(rhs)
return self
def __floordiv__(self, rhs):
return (self.x // self.rhs(rhs)) % self.mod
def __ifloordiv__(self, rhs):
self.x = self.__floordiv__(rhs)
return self
def __pow__(self, rhs):
return pow(self.x, self.rhs(rhs), self.mod)
def __eq__(self, rhs) -> bool:
return self.rhs(rhs) == self.x
def __ne__(self, rhs) -> bool:
return self.rhs(rhs) != self.x
#
import sys
from typing import Any, List
def s() -> str:
"""
stringinput
"""
return sys.stdin.readline().rstrip()
def sl() -> List[str]:
"""
stringinput
"""
return s().split()
def ii() -> int:
"""
int
"""
return int(s())
def il(add_num: int = 0) -> List[int]:
"""
int
"""
return list(map(lambda i: int(i) + add_num, sl()))
def li(n: int, func, *args) -> List[List[Any]]:
"""
"""
return [func(*args) for _ in [0] * n]
# YesNo
def YesNoTemplate(state: bool, upper: bool = False) -> str:
"""
stateTrueupperYes,YESreturn
stateFalseupperNo,NOreturn
"""
YES = ["Yes", "YES"]
NO = ["No", "NO"]
if state:
return YES[int(upper)]
else:
return NO[int(upper)]
def YN(state: bool, upper: bool = False) -> None:
"""
YesNoTemplate
"""
res = YesNoTemplate(state, upper)
print(res)
def YE(state: bool, upper: bool = False) -> bool | None:
"""
boolTrueYesexit
"""
if not state:
return False
YN(True, upper)
exit()
def NE(state: bool, upper: bool = False) -> bool | None:
"""
boolTrueNoexit
"""
if not state:
return False
YN(False, upper)
exit()
def coordinate_check(x: int, y: int, H: int, W: int) -> bool:
"""
0-indexed
"""
return 0 <= x < H and 0 <= y < W
from typing import List, Tuple
def grid_moves(
x: int,
y: int,
H: int,
W: int,
moves: List[Tuple[int]] = [(0, 1), (0, -1), (1, 0), (-1, 0)],
*check_funcs,
) -> List[Tuple[int]]:
"""
moves
xy
HW
moves
check_funcs#
check_funcsxy
False True
"""
res = []
for mx, my in moves:
nx, ny = x + mx, y + my
if not coordinate_check(nx, ny, H, W):
continue
for f in check_funcs:
if not f(nx, ny):
break
else:
res.append((nx, ny))
return res
# DP
from typing import List
def partial_sum_dp(lis: List[int], X: int) -> List[bool]:
"""
dp
lis
dpX
O(X*len(L))
dpbool
"""
dp = [False] * (X + 1)
dp[0] = True
for a in lis:
for k in reversed(range(len(dp))):
if not dp[k]:
continue
if k + a >= len(dp):
continue
dp[k + a] = True
return dp
def knapsack_dp(lis: List[List[int]], W: int) -> List[int]:
"""
dp
lis
w,vwv
dp
dpW
"""
dp = [-(1 << 63)] * (W + 1)
dp[0] = 0
for w, v in lis:
for k in reversed(range(len(dp))):
if w + k >= len(dp):
continue
dp[w + k] = max(dp[w + k], dp[k] + v)
return dp
def article_breakdown(lis: List[List[int]]) -> List[List[int]]:
"""
"""
res = []
for w, v, c in lis:
k = 1
while c > 0:
res.append([w * k, v * k])
c -= k
k = min(2 * k, c)
return res
# ac_library
"""
segtree
Segtree(op,e,v)
op
def op(a,b):
return a+b
e
v
"""
#
#
from collections import deque
from typing import List, Tuple
class Graph:
"""
"""
def __init__(self, N: int, dire: bool = False) -> None:
"""
Ndire
"""
self.N = N
self.dire = dire
self.grath = [[] for _ in [0] * self.N]
self.in_deg = [0] * N
def new_side(self, a: int, b: int):
"""
 0-indexed
ab
ababba
"""
self.grath[a].append(b)
if self.dire:
self.in_deg[b] += 1
if not self.dire:
self.grath[b].append(a)
def side_input(self):
"""
"""
a, b = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b)
def input(self, M: int):
"""
"""
for _ in [0] * M:
self.side_input()
def get(self, a: int):
"""
a
"""
return self.grath[a]
def all(self) -> List[List[int]]:
"""
"""
return self.grath
def topological(self, unique: bool = False) -> List[int]:
"""
unique
uniqueTrue[-1]
"""
if not self.dire:
raise ValueError(" (╥╥)")
in_deg = self.in_deg[:]
S: deque[int] = deque([])
order: List[int] = []
for i in range(self.N):
if in_deg[i] == 0:
S.append(i)
while S:
if unique and len(S) != 1:
return [-1]
cur = S.pop()
order.append(cur)
for nxt in self.get(cur):
in_deg[nxt] -= 1
if in_deg[nxt] == 0:
S.append(nxt)
if sum(in_deg) > 0:
return [-1]
else:
return [x for x in order]
class GraphW:
"""
"""
def __init__(self, N: int, dire: bool = False) -> None:
self.N = N
self.dire = dire
self.grath = [[] for _ in [0] * self.N]
def new_side(self, a: int, b: int, w: int):
"""
 0-indexed
ab
ababba
"""
self.grath[a].append((b, w))
if not self.dire:
self.grath[b].append((a, w))
def side_input(self):
"""
"""
a, b, w = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b, w + 1)
def input(self, M: int):
"""
"""
for _ in [0] * M:
self.side_input()
def get(self, a: int) -> List[Tuple[int]]:
"""
a
"""
return self.grath[a]
def all(self) -> List[List[Tuple[int]]]:
"""
"""
return self.grath
from collections import defaultdict
from typing import List
# UnionFind
class UnionFind:
"""
rollback
UnionFindO(log N)
rollbackO(1)
"""
def __init__(self, n: int) -> None:
self.size = n
self.data = [-1] * n
self.hist = []
def root(self, vtx: int) -> int:
"""
vtx
"""
if self.data[vtx] < 0:
return vtx
return self.root(self.data[vtx])
def same(self, a: int, b: int):
"""
ab
"""
return self.root(a) == self.root(b)
def unite(self, a: int, b: int) -> bool:
"""
ab
root
"""
ra, rb = self.root(a), self.root(b)
#
new_hist = [ra, rb, self.data[ra], self.data[rb]]
self.hist.append(new_hist)
if ra == rb:
return False
if self.data[ra] > self.data[rb]:
ra, rb = rb, ra
self.data[ra] += self.data[rb]
self.data[rb] = ra
return True
def rollback(self):
"""
undo
redo
"""
if not self.hist:
return False
ra, rb, da, db = self.hist.pop()
self.data[ra] = da
self.data[rb] = db
return True
def all(self) -> List[List[int]]:
D = defaultdict(list)
for i in range(self.size):
D[self.root(i)].append(i)
res = []
for l in D.values():
res.append(l)
return res
# Trie
class Trie:
class Data:
def __init__(self, value, ind):
self.count = 1
self.value = value
self.childs = {}
self.ind = ind
def __init__(self):
self.data = [self.Data("ab", 0)] # ab
def add(self, value: str) -> int:
cur = 0
result = 0
#
for t in value:
childs = self.data[cur].childs #
if t in childs:
self.data[childs[t]].count += 1
else:
nd = self.Data(t, len(self.data))
childs[t] = len(self.data)
self.data.append(nd)
result += self.data[childs[t]].count - 1
cur = childs[t]
return result
def lcp_max(self, value: str) -> int:
cur = 0
result = 0
for t in value:
childs = self.data[cur].childs
if t not in childs:
break
if self.data[childs[t]].count == 1:
break
cur = childs[t]
result += 1
return result
def lcp_sum(self, value: str) -> int:
cur = 0
result = 0
for t in value:
childs = self.data[cur].childs
if t not in childs:
break
if self.data[childs[t]].count == 1:
break
cur = childs[t]
result += self.data[childs[t]].count - 1
return result
from typing import List
class BIT:
"""
BIT
1-indexed
O(log n)
"""
def __init__(self, n: int) -> None:
self.n: int = n
self.bit: List[int] = [0] * (n + 1)
def sum(self, i: int) -> int:
"""
i
O(log n)
"""
res = 0
while i:
res += self.bit[i]
i -= -i & i
return res
def interval_sum(self, l: int, r: int) -> int:
"""
lr
l0-indexedr1-indexed
"""
return self.sum(r) - self.sum(l)
def add(self, i: int, x: int):
"""
ix
O(log n)
"""
if i == 0:
raise IndexError("1-indexed")
while i <= self.n:
self.bit[i] += x
i += -i & i
from typing import Tuple
def euclid_dis(x1: int, y1: int, x2: int, y2: int) -> int:
"""
:
sqrt()
sqrt
"""
return ((x1 - x2) ** 2) + ((y1 - y2) ** 2)
def manhattan_dis(x1: int, y1: int, x2: int, y2: int) -> int:
"""
"""
return abs(x1 - x2) + abs(y1 - y2)
def manhattan_45turn(x: int, y: int) -> Tuple[int]:
"""
45
"""
res_x = x - y
res_y = x + y
return res_x, res_y
def chebyshev_dis(x1: int, y1: int, x2: int, y2: int) -> int:
"""
"""
return max(abs(x1 - x2), abs(y1 - y2))
# 便
INF = 1 << 63
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#
N = ii()
S = s()
NE(N % 2 != 0)
YN(True)
A = ""
B = ""
turn = 0
for s in S:
if turn == 0:
A += s
else:
B += s
turn ^= 1
print(A, B)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0