結果
| 問題 |
No.3316 Make 81181819 with only 0,1,or 8
|
| コンテスト | |
| ユーザー |
 hidehic0
|
| 提出日時 | 2025-10-31 21:53:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 42,937 bytes |
| コンパイル時間 | 337 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 78,428 KB |
| 最終ジャッジ日時 | 2025-10-31 21:53:18 |
| 合計ジャッジ時間 | 5,965 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 1 WA * 21 |
ソースコード
r"""
______________________
< this is hidehic0'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
# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.fenwicktree import FenwickTree
# 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)
import io
import os
import sys
from typing import Any
def s() -> str:
"""一行に一つのstringをinput"""
return input()
def sl() -> list[str]:
"""一行に複数のstringをinput"""
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[Any]) -> list[list[Any]]:
"""複数行の入力をサポート"""
return [func(*args) for _ in [0] * n]
# 数学型関数
def is_prime(n: int) -> int:
"""素数判定
計算量は定数時間です。正確には、繰り返し二乗法の計算量によりです
アルゴリズムはミラーラビンの素数判定を使用しています
nが2^64を越えると動作しません
"""
if n == 1:
return False
def f(a, t, n):
x = pow(a, t, n)
nt = n - 1
while t != nt and x not in (1, 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) -> list[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)))
みたいな感じです
最初に素数を列挙するため、普通の素因数分解より効率がいいです
"""
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
return [solve(n) for n in L]
def simple_sigma(n: int) -> int:
"""1からnまでの和
つまり和の公式
"""
return (n * (n + 1)) // 2
def comb(n: int, r: int, mod: int | None = None) -> int:
"""二項係数
高速なはずの二項係数
modを指定すれば、mod付きになる
"""
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
def create_array1(n: int, default=0) -> list[Any]:
"""1次元配列を初期化する関数"""
return [default] * n
def create_array2(a: int, b: int, default=0) -> list[list[Any]]:
"""2次元配列を初期化する関数"""
return [[default] * b for _ in [0] * a]
def create_array3(a: int, b: int, c: int, default=0) -> list[list[list[Any]]]:
"""3次元配列を初期化する関数"""
return [[[default] * c for _ in [0] * b] for _ in [0] * a]
from collections.abc 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
class ChangeMin:
def __init__(self, x) -> None:
"""Change min構造体
代入時現在の値より代入する値が低ければ代入される
setメソッドで代入する
"""
self.x = x
def set(self, new) -> None:
self.x = min(self.x, new)
def val(self) -> any:
return self.x
class ChangeMax:
def __init__(self, x) -> None:
"""Change min構造体
代入時現在の値より代入する値が大きければ代入される
setメソッドで代入する
"""
self.x = x
def set(self, new) -> None:
self.x = max(self.x, new)
def val(self) -> any:
return self.x
def mod_add(a: int, b: int, mod: int) -> int:
"""足し算してmodを取った値を出力
O(1)
"""
return (a + b) % mod
def mod_sub(a: int, b: int, mod: int) -> int:
"""引き算してmodを取った値を出力
O(1)
"""
return (a - b) % mod
def mod_mul(a: int, b: int, mod: int) -> int:
"""掛け算してmodを取った値を出力
O(1)
"""
return (a * b) % mod
def mod_div(a: int, b: int, mod: int) -> int:
"""割り算してmodを取った値を出力
フェルマーの小定理を使って計算します
O(log mod)
"""
return (a * pow(b, -1, mod)) % mod
class ModInt:
def __init__(self, x: int, mod: int = 998244353) -> None:
"""ModInt
リストで使うと参照渡しになるので注意
"""
self.x = x % mod
self.mod = mod
def val(self) -> int:
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
def __hash__(self) -> int:
return hash(self.x)
# YesNo関数
def YesNoTemplate(state: bool, upper: bool = False) -> str:
"""YesNo関数のテンプレート
stateがTrueなら、upperに応じてYes,YESをreturn
stateがFalseなら、upperに応じてNo,NOをreturnする
"""
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:
"""
boolがTrueならYesを出力してexit
"""
if not state:
return False
YN(True, upper)
exit()
def NE(state: bool, upper: bool = False) -> bool | None:
"""
boolがTrueならNoを出力してexit
"""
if not state:
return False
YN(False, upper)
exit()
from collections.abc import Callable
def coordinate_check(x: int, y: int, H: int, W: int) -> bool:
"""座標がグリッドの範囲内にあるかチェックする関数
0-indexedが前提
"""
return 0 <= x < H and 0 <= y < W
def grid_moves(
x: int,
y: int,
H: int,
W: int,
moves: list[tuple[int]] | None = None,
*check_funcs: list[Callable[[int, int], bool]],
) -> list[tuple[int]]:
"""現在の座標から、移動可能な座標をmovesをもとに列挙します。
xとyは現在の座標
HとWはグリッドのサイズ
movesは移動する座標がいくつかを保存する
check_funcsは、その座標の点が#だとかを自前で実装して判定はこちらでするみたいな感じ
なおcheck_funcsは引数がxとyだけというのが条件
追加の判定関数は、弾く場合は、False それ以外ならTrueで
"""
if moves is None:
moves = ([(0, 1), (0, -1), (1, 0), (-1, 0)],)
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
def coordinates_to_id(h: int, w: int) -> tuple[list[list[int]], list[tuple[int, int]]]:
"""座標を一次元のindexに変換する関数
返り値は、
最初のが、座標からid
二つめのが、idから座標
です
"""
ItC = [[-1] * w for _ in [0] * h]
CtI = [(-1, -1) for _ in [0] * (h * w)]
i = 0
for x in range(h):
for y in range(w):
ItC[x][y] = i
CtI[i] = (x, y)
i += 1
return CtI, ItC
import heapq
def dijkstra(
graph: list[list[tuple[int]]],
startpoint: int = 0,
output_prev: bool = False,
) -> list[int] | tuple[list[int], list[int]]:
"""ダイクストラ法のライブラリ
GraphW構造体を使う場合は、allメソッドで、そんまま入れてください
定数倍速いのかは分かりません(いつも使っているフォーマット)
経路復元したい場合は、output_prevをTrueにすればprevも返ってくるので、それを使用して復元してください
0-indexedが前提です
"""
used = [1 << 63] * len(graph)
prev = [-1] * len(graph)
if not 0 <= startpoint < len(graph):
raise IndexError("あのー0-indexedですか?")
used[startpoint] = 0
PQ = [(0, startpoint)]
while PQ:
cos, cur = heapq.heappop(PQ)
if used[cur] < cos:
continue
for nxt, w in graph[cur]:
new_cos = cos + w
if new_cos >= used[nxt]:
continue
used[nxt] = new_cos
prev[nxt] = cur
heapq.heappush(PQ, (new_cos, nxt))
if not output_prev:
return used
return used, prev
def getpath(prev_lis: list[int], goal_point: int) -> list[int]:
"""経路復元ライブラリ
dijkstra関数を使う場合、output_prevをTrueにして返ってきた、prevを引数として用います
他の場合は、移動の時、usedを付けるついでに、prevに現在の頂点を付けてあげるといいです
"""
res = []
cur = goal_point
while cur != -1:
res.append(cur)
cur = prev_lis[cur]
return res[::-1]
# DPのテンプレート
def partial_sum_dp(lis: list[int], X: int) -> list[bool]:
"""部分和dpのテンプレート
lisは品物です
dp配列の長さは、Xにします
計算量は、O(X*len(L))みたいな感じ
返り値は、dp配列で中身は到達できたかを、示すboolです
"""
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) -> int:
"""ナップサックdpのテンプレート
lis: 品物のリスト [[重さ, 価値], ...]
W: ナップサックの容量
戻り値: 最大価値
"""
if W < 0 or not lis:
return 0
dp = [0] * (W + 1)
for w, v in lis:
if w < 0 or v < 0:
msg = "Weight and value must be non-negative"
raise ValueError(msg)
for k in reversed(range(W - w + 1)):
dp[k + w] = max(dp[k + w], dp[k] + v)
return dp[W]
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
def compress_1d(points: list[int] | tuple[int]) -> list[int]:
"""一次元座標圧縮
計算量は、O(N log N)です
lとrは、まとめて入れる事で、座圧できます
"""
d = {num: ind for ind, num in enumerate(sorted(set(points)))}
return [d[a] for a in points]
def compress_2d(points) -> list[tuple[int, int]]:
"""二次元座標圧縮
入力: points - [(x1, y1), (x2, y2), ...] の形式の座標リスト
出力: 圧縮後の座標リストと、元の座標から圧縮後の座標へのマッピング
"""
# x座標とy座標を分離
x_coords = sorted({x for x, y in points}) # 重複を削除してソート
y_coords = sorted({y for x, y in points})
# 座標から圧縮後の値へのマッピング辞書を作成
x_map = {val: idx for idx, val in enumerate(x_coords)}
y_map = {val: idx for idx, val in enumerate(y_coords)}
return [(x_map[x], y_map[y]) for x, y in points]
# ac_libraryのメモ
"""
segtree
初期化するとき
Segtree(op,e,v)
opはマージする関数
例
def op(a,b):
return a+b
eは初期化する値
vは配列の長さまたは、初期化する内容
"""
from collections.abc import Callable
from typing import Any
def rerooting(
G: list[list[int]],
merge: Callable[[Any, Any], Any],
add_root: Callable[[int, Any], Any],
e,
) -> list[Any]:
"""全方位木dp"""
_n = len(G)
dp: list[list[Any]] = [[]] * _n
ans: list[Any] = [e] * _n
def _dfs(u: int, p: int = -1):
nonlocal dp, merge, add_root, e
res: Any = e
dp[u] = [e] * (len(G[u]))
for i, v in enumerate(G[u]):
if v == p:
continue
dp[u][i] = _dfs(v, u)
res = merge(res, dp[u][i])
return add_root(u, res)
def _bfs(u: int, cur: Any, p: int = -1):
nonlocal dp, merge, add_root, e, ans
deg = len(G[u])
for i in range(deg):
if G[u][i] == p:
dp[u][i] = cur
dp_l, dp_r = [e] * (deg + 1), [e] * (deg + 1)
for i in range(deg):
dp_l[i + 1] = merge(dp_l[i], dp[u][i])
for i in reversed(range(deg)):
dp_r[i] = merge(dp_r[i + 1], dp[u][i])
ans[u] = add_root(u, dp_l[deg])
for i in range(deg):
if G[u][i] != p:
_bfs(G[u][i], add_root(u, merge(dp_l[i], dp_r[i + 1])), u)
_dfs(0)
_bfs(0, e)
return ans
def manacher_algorithm(S: str) -> list[int]:
"""Manacher algorithm
res_i = S_iを中心とした最長の回文の半径
"""
# いまいち原理は分からないけどうまいことメモ化してそう
_n = len(S)
res = [0] * _n
i = k = 0
while i < _n:
while i - k >= 0 and i + k < _n and S[i - k] == S[i + k]:
k += 1
res[i] = k
a = 1
while i - a >= 0 and a + res[i - a] < k:
res[i + a] = res[i - a]
a += 1
i += a
k -= a
return res
class RollingHash:
string: str
mod: int
base: int
n: int
def __init__(self, string: str, mod: int = (1 << 61) - 1) -> None:
"""RollingHash構造体
衝突する可能性があるのでmodが違う二つで比較するのが有効
string: 文字列
mod: mod デフォルト値は2^61 - 1
"""
self.string = string
self.mod = mod
self.base = len(set(string))
self.n = n = len(string)
self.pow = [1] * (n + 1)
self.hash = [0] * (n + 1)
for i in range(n):
self.hash[i + 1] = (self.hash[i] * self.base + ord(string[i])) % mod
for i in range(n):
self.pow[i + 1] = self.pow[i] * self.base % mod
def get(self, l: int, r: int) -> int:
"""区間[l,r)のハッシュ値を取得する"""
return (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.mod
def lcp(self, b: int, bn: int) -> int:
"""2つのRollingHashの最長共通接頭辞を返す
bがhashでbnがそのhashの長さです
"""
left, right = 0, min(self.n, bn)
while right - left > 1:
mid = (left + right) // 2
if self.get(0, mid) == b:
left = mid
else:
right = mid
return left
# グラフ構造
# 無向グラフ
from collections import deque
class Graph:
def __init__(self, N: int, dire: bool = False) -> None:
"""グラフ構造体
Nは頂点数、direは有向グラフかです
"""
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) -> None:
"""aとbを辺で繋ぎます
有向グラフなら、aからbだけ、無向グラフなら、aからbと、bからaを繋ぎます
注意 0-indexedが前提
"""
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) -> None:
"""標準入力で、新しい辺を追加します"""
a, b = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b)
def input(self, M: int) -> None:
"""標準入力で複数行受け取り、各行の内容で辺を繋ぎます"""
for _ in [0] * M:
self.side_input()
def get(self, a: int) -> list[int]:
"""頂点aの隣接頂点を出力します"""
return self.grath[a]
def all(self) -> list[list[int]]:
"""グラフの隣接リストをすべて出力します"""
return self.grath
def topological(self, unique: bool = False) -> list[int]:
"""トポロジカルソートします
有向グラフ限定です
引数のuniqueは、トポロジカルソート結果が、一意に定まらないとエラーを吐きます
閉路がある、または、uniqueがTrueで一意に定まらなかった時は、[-1]を返します
"""
if not self.dire:
msg = "グラフが有向グラフでは有りません (╥﹏╥)"
raise ValueError(msg)
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]
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) -> None:
"""aとbを辺で繋ぎます
有向グラフなら、aからbだけ、無向グラフなら、aからbと、bからaを繋ぎます
注意 0-indexedが前提
"""
self.grath[a].append((b, w))
if not self.dire:
self.grath[b].append((a, w))
def side_input(self) -> None:
"""標準入力で、新しい辺を追加します"""
a, b, w = map(lambda x: int(x) - 1, input().split())
self.new_side(a, b, w + 1)
def input(self, M: int) -> None:
"""標準入力で複数行受け取り、各行の内容で辺を繋ぎます"""
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
# UnionFind木
class UnionFind:
def __init__(self, n: int) -> None:
"""UnionFind
rollbackをデフォルトで装備済み
計算量は経路圧縮を行わないため、基本的なUnionFindの動作は、一回あたり、O(log N)
rollbackは、一回あたり、O(1)で行える。
"""
self.size = n
self.data = [-1] * n
self.hist = []
def leader(self, vtx: int) -> int:
"""頂点vtxの親を出力します"""
if self.data[vtx] < 0:
return vtx
return self.leader(self.data[vtx])
def same(self, a: int, b: int) -> bool:
"""aとbが連結しているかどうか判定します"""
return self.leader(a) == self.leader(b)
def merge(self, a: int, b: int) -> bool:
"""aとbを結合します
leaderが同じでも、履歴には追加します
"""
ra, rb = self.leader(a), self.leader(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) -> bool:
"""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.leader(i)].append(i)
return [l for l in D.values()]
class EulerTour:
def __init__(self, edges: list[tuple[int, int, int]], root: int = 0) -> None:
"""オイラーツアーのライブラリ
edges[i] = (u, v, w)
なお閉路がない、連結という前提 エラー処理をしていない
木上の最短経路は、path_query関数を使うこと
初期化にO(N + M) それ以外は、$O(log n)$
Warning:
ac-library-pythonを__init__内で使用しているので注意
定数倍が遅い事に注意 あとメモリも注意 結構リストを使用している
"""
from atcoder.segtree import SegTree
self.edges = edges
self._n = max([max(u, v) for u, v, w in edges]) + 1
self.root = root
self.graph: list[list[tuple[int, int, int]]] = [[] for _ in [0] * self._n]
for i, (u, v, w) in enumerate(edges):
self.graph[u].append((v, w, i))
self.graph[v].append((u, w, i))
self._build()
self.segtree_edgecost = SegTree(lambda a, b: a + b, 0, self.edge_cost)
self.segtree_depth = SegTree(
min,
(1 << 63, 1 << 63),
[(d, i) for i, d in enumerate(self.depth)],
)
def _build(self) -> None:
self.euler_tour: list[tuple[int, int]] = [(0, -1)]
self.edge_cost: list[int] = [0]
self.depth: list[int] = [0]
def dfs(cur: int, p: int = -1, d: int = 0) -> None:
for nxt, w, i in self.graph[cur]:
if nxt == p:
continue
self.euler_tour.append((nxt, i))
self.edge_cost.append(w)
self.depth.append(d + 1)
dfs(nxt, cur, d + 1)
self.euler_tour.append((cur, i))
self.edge_cost.append(-w)
self.depth.append(d)
dfs(self.root)
self.first_arrival = [-1] * self._n
self.last_arrival = [-1] * self._n
self.first_arrival[self.root] = 0
self.last_arrival[self.root] = len(self.euler_tour) - 1
self.edge_plus = [-1] * (self._n - 1)
self.edge_minus = [-1] * (self._n - 1)
for i, (u, edge_ind) in enumerate(self.euler_tour):
if self.edge_cost[i] >= 0:
self.edge_plus[edge_ind] = i
else:
self.edge_minus[edge_ind] = i
if self.first_arrival[u] == -1:
self.first_arrival[u] = i
self.last_arrival[u] = i
def lca(self, a: int, b: int) -> int:
l, r = (
min(self.first_arrival[a], self.first_arrival[b]),
max(self.last_arrival[a], self.last_arrival[b]),
)
return self.euler_tour[self.segtree_depth.prod(l, r)[1]][0]
def path_query_from_root(self, u: int) -> int:
assert 0 <= u < self._n
return self.segtree_edgecost.prod(0, self.first_arrival[u] + 1)
def path_query(self, a: int, b: int) -> int:
"""aからbへの最短経路"""
try:
l = self.lca(a, b)
except IndexError:
return 0
return (
self.path_query_from_root(a)
+ self.path_query_from_root(b)
- (2 * self.path_query_from_root(l))
)
def change_edge_cost(self, i: int, w: int) -> None:
self.segtree_edgecost.set(self.edge_plus[i], w)
self.segtree_edgecost.set(self.edge_minus[i], -w)
class PotentialUnionFind:
def __init__(self, n: int) -> None:
"""重み付きunionfind
俗に言う、牛ゲー
uniteは、差を指定して、uniteします
"""
self.data: list[int] = [-1] * n
self.pot: list[int] = [0] * n
def root(self, vtx: int) -> int:
"""頂点vtxの親を出力します
ポテンシャルは出力しません
"""
if self.data[vtx] < 0:
return vtx
rt = self.root(self.data[vtx])
self.pot[vtx] += self.pot[self.data[vtx]]
self.data[vtx] = rt
return rt
def potential(self, vtx: int) -> int:
"""頂点vtxのポテンシャルを出力します"""
self.root(vtx)
return self.pot[vtx]
def same(self, a: int, b: int) -> bool:
"""頂点aと頂点bが同じ連結成分かを判定します"""
return self.root(a) == self.root(b)
def unite(self, a: int, b: int, p: int) -> bool:
"""頂点aから頂点bを、pの距離でmergeします
計算量はlog nです
"""
p += self.potential(b) - self.potential(a)
a, b = self.root(a), self.root(b)
if a == b:
return False
if self.data[a] < self.data[b]:
a, b = b, a
p *= -1 # ポテンシャルもswapします
self.data[b] += self.data[a]
self.data[a] = b
self.pot[a] = p
return True
def diff(self, a: int, b: int) -> int:
"""頂点aから頂点bの距離を、出力します"""
return self.potential(a) - self.potential(b)
from collections.abc import Callable
from typing import Any
def _keys_for_heapq(x: Any):
"""先頭の値を取得する"""
cur = x
while True:
try:
cur = cur[0]
except TypeError:
break
return cur
class HeapBase:
def __init__(
self,
arr: list[Any] = [],
key: Callable[[Any], Any] = _keys_for_heapq,
) -> None:
"""arrはソート済みが前提です"""
self.key: Callable[Any, Any] = key
self.lis: list[tuple[Any, Any]] = [(self.key(x), x) for x in arr]
def _op(self, a: int, b: int) -> bool:
# aが親 bが子って感じだよ
assert 0 <= a < b < len(self.lis)
return True
def push(self, x: Any) -> None:
self.lis.append((self.key(x), x))
i = len(self.lis) - 1
while i != 0:
p = (i - 1) // 2
if self._op(p, i):
self.lis[i], self.lis[p] = self.lis[p], self.lis[i]
i = p
else:
break
def pop(self) -> Any:
assert len(self.lis) > 0
res = self.lis[0][1] # Return the original value (not the key)
self.lis[0] = self.lis[-1] # Move the last element to the root
self.lis.pop() # Remove the last element
if not self.lis: # If the heap is empty, return early
return res
# Restore heap property by sifting down
i = 0
while i * 2 + 1 < len(self.lis): # While there is at least one child
c1 = i * 2 + 1 # Left child
c2 = i * 2 + 2 # Right child
# Pick the smaller of the two children (if right child exists)
smallest = c1
if c2 < len(self.lis) and self._op(c1, c2):
smallest = c2
# If the parent is larger than the smallest child, swap
if self._op(i, smallest):
self.lis[i], self.lis[smallest] = self.lis[smallest], self.lis[i]
i = smallest
else:
break
return res
def __len__(self) -> int:
return len(self.lis)
def __getitem__(self, i: int):
return self.lis[i][1]
class HeapMin(HeapBase):
def _op(self, a: int, b: int) -> bool:
return self.lis[a][0] > self.lis[b][0]
class HeapMax(HeapBase):
def _op(self, a: int, b: int) -> bool:
return self.lis[a][0] < self.lis[b][0]
# Trie木
class Trie:
class Data:
"""trie木のノード"""
def __init__(self, value, ind):
"""trie木のノード"""
self.count = 1
self.value = value
self.childs = {}
self.ind = ind
def __init__(self):
"""Trie木"""
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
import math
from collections.abc import Callable
from typing import Any
def mo_algorithm(
N: int,
queries: list[Any],
add: Callable[[int], Any],
delete: Callable[[int], Any],
getvalue: Callable[[], Any],
) -> list[Any]:
"""Mo's algorithm
queriesは、(左端, 右端)で1-indexed
addはあるindexが追加される時の値を現在の値にする
deleteはあるindexが削除される時の値を現在の値にする
getvalueは現在の値を返す
"""
Q = len(queries)
res = [None] * Q
M = int(max(1, 1.0 * N / max(1, math.sqrt(Q * 2.0 / 3.0))))
queries = [(l, r, i) for i, (l, r) in enumerate(queries)]
queries.sort(key=lambda x: (x[0] // M, x[1] if (x[0] // M) % 2 == 0 else -x[1]))
cl, cr = 0, -1
for l, r, ind in queries:
l -= 1
r -= 1
while cl > l:
cl -= 1
add(cl)
while cr < r:
cr += 1
add(cr)
while cl < l:
delete(cl)
cl += 1
while cr > r:
delete(cr)
cr -= 1
res[ind] = getvalue()
return res
import math
from collections.abc import Callable
from typing import Any
class SquareDivision:
def __init__(self, lis: list[Any], op: Callable[[Any, Any], Any]) -> None:
"""平方分割ライブラリ
ほぼACLのセグ木と同じ
"""
self.n = len(lis)
self.op = op
self.block_size = math.isqrt(self.n)
self.blocks = []
self.lis = lis[:]
for i in range(0, self.n, self.block_size):
block_val = lis[i]
for k in range(i + 1, min(i + self.block_size, self.n)):
block_val = self.op(block_val, lis[k])
self.blocks.append(block_val)
self.m = len(self.blocks)
def get_block_index_left(self, i: int) -> int:
return i // self.block_size
def get_block_index_right(self, i: int) -> int:
return (i + self.block_size - 1) // self.block_size
def prod(self, l: int, r: int) -> Any:
"""rは0-indexedなのに注意してください"""
assert 0 <= l <= r < self.n
l_block_left = self.get_block_index_left(l)
r_block_left = self.get_block_index_left(r)
if l_block_left == r_block_left:
res = self.lis[l]
for k in range(l + 1, r + 1):
res = self.op(res, self.lis[k])
return res
res = self.lis[l]
for i in range(l + 1, min((l_block_left + 1) * self.block_size, self.n)):
res = self.op(res, self.lis[i])
for block_ind in range(l_block_left + 1, r_block_left):
res = self.op(res, self.blocks[block_ind])
for i in range(r_block_left * self.block_size, r + 1):
res = self.op(res, self.lis[i])
return res
def update(self, i: int, x: Any) -> None:
assert 0 <= i < self.n
self.lis[i] = x
block_ind = self.get_block_index_left(i)
start = block_ind * self.block_size
end = min(start + self.block_size, self.n)
if start < self.n:
self.blocks[block_ind] = self.lis[start]
for j in range(start + 1, end):
self.blocks[block_ind] = self.op(self.blocks[block_ind], self.lis[j])
def get(self, i: int) -> Any:
assert 0 <= i < self.n
return self.lis[i]
class SquareDivisionSpeedy(SquareDivision):
def __init__(
self,
lis: list[Any],
op: Callable[[Any, Any], Any],
delete: Callable[[Any, Any], Any],
) -> None:
"""その値を削除する関数がある場合の平方分割ライブラリ
更新は高速だがクエリがボトルネックなのであまり変わらない
"""
self.delete = delete
super().__init__(lis, op)
def update(self, i: int, x: Any) -> None:
assert 0 <= i < self.n
block_ind = self.get_block_index_left(i)
self.blocks[block_ind] = self.delete(self.blocks[block_ind], self.lis[i])
self.lis[i] = x
self.blocks[block_ind] = self.op(self.blocks[block_ind], self.lis[i])
class PrefixSum2D:
def __init__(self, h: int, w: int) -> None:
"""二次元累積和のライブラリ"""
self.data = [[0] * (w + 1) for _ in [0] * (h + 1)]
self.builded = False
self.h = h
self.w = w
def add(self, x: int, y: int, a: int) -> None:
assert 0 <= x < self.h and 0 <= y < self.w
self.data[x + 1][y + 1] += a
def build(self) -> None:
assert not self.builded
for i in range(self.h + 1):
for k in range(self.w):
self.data[i][k + 1] += self.data[i][k]
for k in range(self.w + 1):
for i in range(self.h):
self.data[i + 1][k] += self.data[i][k]
self.builded = True
def prod(self, ax: int, ay: int, bx: int, by: int) -> int:
assert 0 <= ax <= bx < self.h and 0 <= ay <= by < self.w
assert self.builded
return (
self.data[bx + 1][by + 1]
+ self.data[ax][ay]
- self.data[ax][by + 1]
- self.data[bx + 1][ay]
)
from collections.abc import Callable
from typing import Any
class DualSegmentTree:
def __init__(self, op: Callable[[Any, Any], Any], e, n: int) -> None:
"""区間作用/一点取得のセグメント木
opは区間作用用の関数
eは初期値
vは長さ
"""
self._op: Callable[[Any, Any], Any] = op
self._e: Any = e
self._n: int = n
self.n: int = 1 << (n - 1).bit_length()
self.data = [e] * (self.n * 2)
def apply(self, l, r, x) -> None:
"""区間[l,r)にxを適用"""
assert 0 <= l <= r <= self.n
l += self.n
r += self.n
while l < r:
if l & 1:
self.data[l] = self._op(self.data[l], x)
l += 1
if r & 1:
self.data[r - 1] = self._op(self.data[r - 1], x)
l >>= 1
r >>= 1
def get(self, p: int) -> Any:
"""pの値を取得する"""
assert 0 <= p < self.n
res = self._e
p += self.n
while p:
res = self._op(res, self.data[p])
p >>= 1
return res
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")
MOVES1 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
MOVES2 = MOVES1 + [(1, 1), (1, -1), (-1, 1), (-1, -1)]
# コード
T = int(input())
for _ in [0] * T:
N = ii()
K = 81181819
L = [int(t) for t in str(K - N)][::-1]
res = []
for i in range(len(L)):
l = []
if L[i] >= 8:
l.append(8)
L[i] -= 8
l += [1] * L[i]
for k in range(len(l)):
if len(res) <= k:
res.append(l[k] * (10**i))
else:
res[k] += l[k] * (10**i)
print(len(res))
for k in res:
print(k)