結果
| 問題 |
No.3127 Multiple of Twin Prime
|
| ユーザー |
 Apollo@Kuro
|
| 提出日時 | 2025-01-19 23:37:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 31,130 bytes |
| コンパイル時間 | 781 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 78,464 KB |
| 最終ジャッジ日時 | 2025-01-20 14:19:34 |
| 合計ジャッジ時間 | 4,370 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | AC * 2 WA * 9 |
ソースコード
def main():
T = int(input())
KASU = [15, 35, 143, 323, 899, 1763, 3599, 5183, 10403, 11663, 19043, 22499, 32399, 36863, 39203, 51983, 57599, 72899, 79523, 97343, 121103, 176399, 186623, 213443, 272483, 324899, 359999, 381923, 412163, 435599, 656099, 675683, 685583, 736163, 777923, 1040399, 1065023, 1102499, 1127843, 1192463, 1327103, 1512899, 1633283, 1664099, 1695203, 1742399, 2039183, 2108303, 2196323, 2214143, 2585663, 2624399, 2782223, 2883203, 2965283, 3196943, 3504383, 3526883, 3732623, 3802499, 3992003, 4112783, 4334723, 4359743, 4460543, 4536899, 4588163, 5008643, 5143823, 5336099, 5475599, 5673923, 6502499, 6718463, 7064963, 7225343, 7354943, 7452899, 7784099, 7851203, 8820899, 8999999, 9734399, 10036223, 10575503, 10614563, 10889999, 11088899, 11289599, 11370383, 11492099, 11985443, 12027023, 12446783, 12531599, 12659363, 12830723, 13483583, 14197823, 14607683, 14837903, 15350723, 15444899, 16016003, 16160399, 16402499, 16744463, 17040383, 17288963, 17791523, 17892899, 17994563, 18147599, 18249983, 18818243, 19554083, 20088323, 20412323, 20684303, 21511043, 21622499, 22297283, 22924943, 23039999, 24324623, 24681023, 25100099, 25220483, 26009999, 27373823, 27878399, 29354723, 29615363, 30008483, 30272003, 30470399, 31809599, 31945103, 32012963, 32970563, 34222499, 34433423, 34574399, 37088099, 37601423, 38415203, 39312899, 39689999, 40449599, 41602499, 42928703, 43164899, 44355599, 44756099, 44916803, 45724643, 45968399, 46131263, 46621583, 47196899, 48274703, 48441599, 50808383, 52012943, 53406863, 53758223, 54022499, 55621763, 56070143, 56972303, 57153599, 57608099, 60186563, 62062883, 63202499, 64160099, 65415743, 67568399, 67765823, 68757263, 70358543, 71064899, 72897443, 73925603, 74442383, 77792399, 78110243, 78535043, 80460899, 80999999, 81216143, 81757763, 85377599, 86155523, 87272963, 88736399, 88962623, 89075843, 89529443, 92736899, 93663683, 94478399, 95413823, 97180163, 98604899, 100160063, 100761443, 101364623, 101848463, 102819599, 105513983, 106131203, 106750223, 108743183, 109369763, 110249999, 110880899, 114704099, 117939599, 118592099, 119639843, 122279363, 122544899, 123609923, 124545599, 124813583, 128867903, 132020099, 133402499, 136889999, 137311523, 138721283, 139996223, 142563599, 143280899, 145009763, 145733183, 146603663, 147914243, 149817599, 150111503, 153214883, 157251599, 159062543, 164403683, 166874723, 169052003, 169208063, 174715523, 177902243, 179506403, 187142399, 187470863, 187964099, 188293283, 189282563, 191268899, 192598883, 193265603, 194100623, 195944003, 196280099, 198302723, 203062499, 205119683, 207014543, 208744703, 211702499, 212051843, 212926463, 213978383, 221057423, 229159043, 233172899, 233722943, 235008899, 235929599, 242798723, 244672163, 244859903, 247495823, 247684643, 252428543, 255104783, 257987843, 258180623, 260499599, 262051343, 263412899, 267715043, 270668303, 276623423, 277222499, 278622863, 283248899, 285677603, 288320399, 289952783, 295496099, 296115263, 299013263, 302342543, 303386723, 305900099, 309056399, 309689603, 311804963, 312653123, 314991503, 316484099, 318194243, 320768099, 321198083, 322489763, 323568143, 325513763, 325730303, 326163599, 328334399, 328769423, 333135503, 334450943, 335329343, 343064483, 343731599, 357663743, 357890723, 364046399, 366339599, 367949123, 369100943, 375584399, 377214083, 377447183, 379080899, 381889763, 388011203, 390141503, 393704963, 395612099, 398481443, 399680063, 400880483, 405941903, 409333823, 414448163, 417875363, 419348483, 420578063, 422302499, 426009599, 429235523, 430479503, 431475983, 432972863, 436726403, 440244323, 441504143, 441756323, 443523599, 449100863, 454457123, 457018883, 461906063, 463196483, 464747363, 466041743, 466559999, 467078543, 468635903, 472540643, 476985599, 485673443, 488056463, 488852099, 490976963, 496041983, 496309283, 500327423, 505440323, 508141763, 509495183, 511664399, 512479043, 515199203, 517107599, 522579599, 527253443, 530288783, 530841599, 531671363, 538332803, 542517263, 546156899, 554037443, 555167843, 558282383, 560268899, 561121343, 563682563, 567964223, 571688099, 581195663, 584672399, 593994383, 596336399, 620906723, 623900483, 626601023, 633528899, 640191203, 640494863, 645668099, 648720899, 654234083, 655462403, 665639999, 668119103, 672468623, 675896003, 681836543, 689062499, 689692643, 711929123, 712889999, 713530943, 714492899, 721567043, 722534399, 723179663, 726410303, 732243599, 734843663, 742017599, 744307523, 751198463, 755150399, 757790783, 758451599, 760766723, 766736099, 769396643, 770062499, 772395263, 779414723, 780755363, 789497603, 790172099, 794225123, 799645283, 801342863, 803722499, 807128099, 814988303, 816359183, 819104399, 821510243, 826677503, 842276483, 848556899, 853107263, 863654543, 864359999, 874266623, 880308899, 885657599, 892814399, 900720143, 905408099, 908299043, 916272899, 923552099, 928299023, 929762063, 933791363, 951105599, 951845903, 952956899, 965966399, 968578883, 970447103, 972317123, 976437503, 980942399, 985457663, 993006143, 994897763, 1006285283, 1006665983, 1009332899, 1014295103, 1025792783, 1027715363, 1031565923, 1033108163, 1036196099, 1043160803, 1044711683, 1047816899, 1050537743, 1052483363, 1058331023, 1060283843, 1063412099, 1070467523, 1075971203, 1077940223, 1083068099, 1085043599, 1087020899, 1093757183, 1098922499, 1100912399, 1108090943, 1110888899, 1112089103, 1128153743, 1128959999, 1130169923, 1139062499, 1140277823, 1143116099, 1144333583, 1158177023, 1164720383, 1166768963, 1170460943, 1173747599, 1176627203, 1181159423, 1188180899, 1190249999, 1191078143, 1196468099, 1200622499, 1208118563, 1213964963, 1214383103, 1222341443, 1228642703, 1230746723, 1244678399, 1256560703, 1260818063, 1262523023, 1266790463, 1276632899, 1281783203, 1284362243, 1288666403, 1296864143, 1303787663, 1320740963, 1329915023, 1334294783, 1352768399, 1353651263, 1361609999, 1363824899, 1370480399, 1383839999, 1391886863, 1394126243, 1395919043, 1409852303, 1411655183, 1413008099, 1420686863, 1427479523, 1429747343, 1443392063, 1462144643, 1469035583, 1478248703, 1479171599, 1487490623, 1490732099, 1493977103, 1495368899, 1498618943, 1501407503, 1514922083, 1524277763, 1533662243, 1538835983, 1539777599, 1547792963, 1550154383, 1561040099, 1586269583, 1587225599, 1603041443, 1610256383, 1612183103, 1634423183, 1642680899, 1651447043, 1656327203, 1668559103, 1692664163, 1695627683, 1697604803, 1700077823, 1712966543, 1714953743, 1723910399, 1731392099, 1743897599, 1751422499, 1760473763, 1762488323, 1765512323, 1770053183, 1779152399, 1782697283, 1787767523, 1798438463, 1803021443, 1812204899, 1818340163, 1823460803, 1835265599, 1840409999, 1853302499, 1876622399, 1883386403, 1895905763, 1899042083, 1901657663, 1905322499, 1916863523, 1917388943, 1926332099, 1932657443, 1938464783, 1943751743, 1947456899, 1953816803, 1959655823, 1960718399, 1969761923, 1983099023, 1991122883, 1998089999, 2004531983, 2035814399, 2037439043, 2041232399, 2053721123, 2055896963, 2078265743, 2099655683, 2120602499, 2124472463, 2132777123, 2141097983, 2144430863, 2148322499, 2156673599, 2170628099, 2179022399, 2187432899, 2191925123, 2193048899, 2214455363, 2222933903, 2242211903, 2245622543, 2248466723, 2271284963, 2275289999, 2276434943, 2279298563, 2282737283, 2285604863, 2315534399, 2334049343, 2343334463, 2350310399, 2356131599, 2366627903, 2369547683, 2374807823, 2379488399, 2383587683, 2387104163, 2388276899, 2400020099, 2404137023, 2412970883, 2417688899, 2420639999, 2428321283, 2433646223, 2437199423, 2439569663, 2441348099, 2453220899, 2455004303, 2466910223, 2474067599, 2478844943, 2492006399, 2493803843, 2499200063, 2502200483, 2505202703, 2513016899, 2526268643, 2546211599, 2555302499, 2559550463, 2589995663, 2597940899, 2607123599, 2614481423, 2621235203, 2625537599, 2636000963, 2636617103, 2644016399, 2645867843, 2650190399, 2674958399, 2679925823, 2686141583, 2690496899, 2701088783, 2711076623, 2722961123, 2734244099, 2741779043, 2760661763, 2778344099, 2794179599, 2798621603, 2818335743, 2824709903, 2827261583, 2833645823, 2837479823, 2838758399, 2867602499, 2872102463, 2874032099, 2885623523, 2904994403, 2917296143, 2959577603, 2961536399, 2970032003, 2974611599, 2979194723, 2984436899, 3015986723, 3030502499, 3049027523, 3061630223, 3062294243, 3073593599, 3093584399, 3094919423, 3098258243, 3115649123, 3125033603, 3128388623, 3140481599, 3147209999, 3159339263, 3162712643, 3166087823, 3189764483, 3192476003, 3195867023, 3203333603, 3216250943, 3227148863, 3236699663, 3238748099, 3240114083, 3270924863, 3274357283, 3279852899, 3286728899, 3288793103, 3309470783, 3312923363, 3339915263, 3352409999, 3376772099, 3381655103, 3383748899, 3390732899, 3406823423, 3409625663, 3415233599, 3416636303, 3434194403, 3456028943, 3470152463, 3482180099, 3483596483, 3487138703, 3505587263, 3507008399, 3523372163, 3530498723, 3533351363, 3536918783, 3555498383, 3560508899, 3610808099, 3612250403, 3620188223, 3631026563, 3678179903, 3679635599, 3692020643, 3707348543, 3708809999, 3711002723, 3739567103, 3761614223, 3767504399, 3778560899, 3789633599, 3841520399, 3860136899, 3861628163, 3867596099, 3881040803, 3959933183, 3965220899, 3966732323, 3967488143, 3972780899, 3993987203, 4008409343, 4018292099, 4022096399, 4043433743, 4044959999, 4051067903, 4056416099, 4075545599, 4115479103, 4120099343, 4134747203, 4154060303, 4170318083, 4181174243, 4196707523, 4209154883, 4214606399, 4228640783, 4238009999, 4247389583, 4259911823, 4283440703, 4292870399, 4295229443, 4300736399, 4316489999, 4318855523, 4320432899, 4334642243, 4346501183, 4353624323, 4370267663, 4403649599, 4431564899, 4455562499, 4469189903, 4482034703, 4507779599, 4514227343, 4517452943, 4518259523, 4525521983, 4544108099, 4546535183, 4566786083, 4591146563, 4614756623, 4639244543, 4652331263, 4662158399, 4685128703, 4690880099, 4721338943, 4736192399, 4744454399, 4746934403, 4765140899, 4781722499, 4787532863, 4796670563, 4816637603, 4829138063, 4829972003, 4863388643, 4866736643, 4875949583, 4880140163, 4890204899, 4900280003, 4917094883, 4919619599, 4925513123, 4928039999, 4953344399, 4964329763, 4968558143, 4980407183, 4987184399, 5018588963, 5023690883, 5029646399, 5033902499, 5038160399, 5040716003, 5078272643, 5087683583, 5089395599, 5096246543, 5099673743, 5108246783, 5119402499, 5142610943, 5156388863, 5166734399, 5196968099, 5198698403, 5208220223, 5216017283, 5216883983, 5220351503, 5222952899, 5251611023, 5277731903, 5281219583, 5310036899, 5334549443, 5338055843, 5381983043, 5418137663, 5428742399, 5453527103, 5490809999, 5499705599, 5505936803, 5532681923, 5537145743, 5551442063, 5566652099, 5582779523, 5584572899, 5589057599, 5626800143, 5650228223, 5656544099, 5683652099, 5685461603, 5706291599, 5718081923, 5731701263, 5774480099, 5776304003, 5788166399, 5800040963, 5815587599, 5832071423, 5840322083, 5858677763, 5875222499, 5902848899, 5909304383, 5923149443, 5965708643, 5969416643, 5970343823, 5993546723, 6002840483, 6004700099, 6014002499, 6035425343, 6039154943, 6105547043, 6113988863, 6152519843, 6163820099, 6168531599, 6173244899, 6206288399, 6223316543, 6237524483, 6265039103, 6277392899, 6304042403, 6329793599, 6341255423, 6350814863, 6351771203, 6369955343, 6374744963, 6384329603, 6399680003, 6423701903, 6433323263, 6437173823, 6471880703, 6475742783, 6478640099, 6500874383, 6507648899, 6509585123, 6520239503, 6525085283, 6533812223, 6546428099, 6563916323, 6567805763, 6568778303, 6593115203, 6606763523, 6621402383, 6650728703, 6666395903, 6675216803, 6707609999, 6712524899, 6719408783, 6725312063, 6730233443, 6746979599, 6759799523, 6781522499, 6801300899, 6811200899, 6816153599, 6842929283, 6843921983, 6848886563, 6857827343, 6870752099, 6925568399, 6927565823, 6933559823, 6945555599, 6955559999, 6982607843, 6995649599, 7008703523, 7066083599, 7086272399, 7093345283, 7109525123, 7114585103, 7121672099, 7143968483, 7162236899, 7192736099, 7200880163, 7202916899, 7221260483, 7240648463, 7259039999, 7281550223, 7286671043, 7297943183, 7302044303, 7330784399, 7339006223, 7364729123, 7366788899, 7384308623, 7400816783, 7415276543, 7446309263, 7456667903, 7459776899, 7487787023, 7504410383, 7556477183, 7571088143, 7589894399, 7595122499, 7600352399, 7607677283, 7612911503, 7658000099, 7663251599, 7666403363, 7671657743, 7679016899, 7681120163, 7694798399, 7736961599, 7744352003, 7789827599, 7803602243, 7826940899, 7848188099, 7851377663, 7860950243, 7885439999, 7887571343, 7888637123, 7933464899, 8013830399, 8021351843, 8027801603, 8038556963, 8040708899, 8067632399, 8081650403, 8103240323, 8112965183, 8135679203, 8167098383, 8172521603, 8179031843, 8195318783, 8211621923, 8222499683, 8248635683, 8295566399, 8298845603, 8304312383, 8306499599, 8308687103, 8348111423, 8364565763, 8385431183, 8429443343, 8458113023, 8496783683, 8504528399, 8534433923, 8537759999, 8548851599, 8568834623, 8582169599, 8587728899, 8589953123, 8609984099, 8623351043, 8641189763, 8673569423, 8693697599, 8695935503, 8701531523, 8738510399, 8740754063, 8753099363, 8780064803, 8791312643, 8800316099, 8814956543, 8819463743, 8837504063, 8856692099, 8864599103, 8893998863, 8901922499, 8910982403, 8918913599, 8935920899, 8938189763, 8941593599, 8958622499, 8996143103, 9015502499, 9041727743, 9061136099, 9069133823, 9109175363, 9175724099, 9178023203, 9207937763, 9213696143, 9250592399, 9258673283, 9279468899, 9329241743, 9358240643, 9369852803, 9374499683, 9409388003, 9439676963, 9442008899, 9467679203, 9480527423, 9482864399, 9506249999, 9515612303, 9521466083, 9527321663, 9535522499, 9562492943, 9573056963, 9574231103, 9576579599, 9605960099, 9662496803, 9667215683, 9680198543, 9714467843, 9729849599, 9744058943, 9747612899, 9763020863, 9774881423, 9780814403, 9783188099, 9786749183, 9827153423, 9828343043, 9852150563, 9870025103, 9905822783, 9941685263, 9944078399, 9998000099]
for i in range(T):
N = int(input())
print(KASU[bisect_left(KASU, N + 1) - 1] if N > 5 else -1)
pass
""""""""""""""""""""""""""
##########################
""""""""""""""""""""""""""
from heapq import *
from bisect import *
from itertools import *
from collections import *
from functools import cache
from math import *
import sys
sys.setrecursionlimit(10**9)
sys.set_int_max_str_digits(0)
MOD1= 998244353
MOD2 = 10 ** 9 + 7
INF = 1 << 60
eng = "abcdefghijklmnopqrstuvwxyz"
ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
dist1 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
dist2 = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (-1, 1), (1, -1)]
acc = accumulate
dd = defaultdict
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
self.member = [[i] for i in range(n)]
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def merge(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
self.member[x] += self.member[y]
self.member[x] = sorted(self.member[x], reverse=True)[:10]
def same(self, x, y):
return self.find(x) == self.find(y)
class SegmentTree:
def __init__(self, data, func, default):
self.n = len(data)
self.func = func
self.default = default
self.tree = [default] * (2 * self.n)
for i in range(self.n):
self.tree[self.n + i] = data[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i + 1])
def set(self, index, value):
index += self.n
self.tree[index] = value
while index > 1:
index //= 2
self.tree[index] = self.func(self.tree[2 * index], self.tree[2 * index + 1])
def prod(self, left, right):
left += self.n
right += self.n
res = self.default
while left < right:
if left % 2:
res = self.func(res, self.tree[left])
left += 1
if right % 2:
right -= 1
res = self.func(res, self.tree[right])
left //= 2
right //= 2
return res
def get(self, index):
return self.tree[self.n + index]
def all_prod(self):
return self.tree[1]
def max_right(self, left, cond):
left += self.n
sm = self.default
while True:
while left % 2 == 0:
left //= 2
if not cond(self.func(sm, self.tree[left])):
while left < self.n:
left *= 2
if cond(self.func(sm, self.tree[left])):
sm = self.func(sm, self.tree[left])
left += 1
return left - self.n
sm = self.func(sm, self.tree[left])
left += 1
if (left & -left) == left:
break
return self.n
def min_left(self, right, cond):
right += self.n
sm = self.default
while True:
right -= 1
while right > 1 and right % 2 == 1:
right //= 2
if not cond(self.func(self.tree[right], sm)):
while right < self.n:
right = 2 * right + 1
if cond(self.func(self.tree[right], sm)):
sm = self.func(self.tree[right], sm)
right -= 1
return right + 1 - self.n
sm = self.func(self.tree[right], sm)
if (right & -right) == right:
break
return 0
def SUM(a, b):
return a + b
def PRODUCT(a, b):
return a * b
def MAX(a, b):
return max(a, b)
def MIN(a, b):
return min(a, b)
def XOR(a, b):
return a ^ b
def GCD(a, b):
return gcd(a, b)
def LCM(a, b):
return a * b // gcd(a, b) if a and b else 0
def get_prime(n):
sieve = [True] * (n + 1)
i = 2
while i * i <= n:
if sieve[i]:
for j in range(i * i, n + 1, i):
sieve[j] = False
i += 1
return [i for i in range(2, n + 1) if sieve[i]]
class Dijkstra:
def __init__(self, graph):
self.graph = graph
def shortest_path(self, start, goal=None):
# 初期化
distances = {node: float('inf') for node in self.graph}
distances[start] = 0
priority_queue = [(0, start)]
previous_nodes = {node: None for node in self.graph}
while priority_queue:
current_distance, current_node = heappop(priority_queue)
# 最短距離が既知の距離より大きい場合はスキップ
if current_distance > distances[current_node]:
continue
# 隣接ノードをチェック
for neighbor, weight in self.graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node
heappush(priority_queue, (distance, neighbor))
# ゴールが指定されており、到達した場合は終了
if goal is not None and current_node == goal:
break
return distances, previous_nodes
def reconstruct_path(self, start, goal, previous_nodes):
path = []
current = goal
while current is not None:
path.append(current)
current = previous_nodes[current]
path.reverse()
if path[0] == start:
return path
else:
return [] # 経路が存在しない場合
class WeightedUnionFind: #重み付きunion-find
def __init__(self, N):
self.N = N
self.parents = [-1] * N
self.rank = [0] * N
self.weight = [0] * N
def root(self, x):
if self.parents[x] == -1:
return x
rx = self.root(self.parents[x])
self.weight[x] += self.weight[self.parents[x]]
self.parents[x] = rx
return self.parents[x]
def get_weight(self, x):
self.root(x)
return self.weight[x]
def unite(self, x, y, d):
'''
A[x] - A[y] = d
'''
w = d + self.get_weight(x) - self.get_weight(y)
rx = self.root(x)
ry = self.root(y)
if rx == ry:
_, d_xy = self.diff(x, y)
if d_xy == d:
return True
else:
return False
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
w = -w
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.parents[ry] = rx
self.weight[ry] = w
return True
def is_same(self, x, y):
return self.root(x) == self.root(y)
def diff(self, x, y):
if self.is_same(x, y):
return True, self.get_weight(y) - self.get_weight(x)
else:
return False, 0
def make_divisors(n):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
# N進数変換
def base_n(num_10, n):
str_n = ''
while num_10:
if num_10 % n >= 10:
return -1
str_n += str(num_10 % n)
num_10 //= n
return int(str_n[::-1])
class SortedList:
def __init__(self, iterable=None):
self._list = []
self._min = None # 最小値のキャッシュ
self._max = None # 最大値のキャッシュ
if iterable:
self.update(iterable)
def add(self, value):
"""値を追加してソートを維持します"""
insort(self._list, value)
if self._min is None or value < self._min:
self._min = value
if self._max is None or value > self._max:
self._max = value
def remove(self, value):
index = bisect_left(self._list, value)
if index < len(self._list) and self._list[index] == value:
self._list.pop(index)
if value == self._min or value == self._max:
self._min = self._list[0] if self._list else None
self._max = self._list[-1] if self._list else None
else:
raise ValueError(f"{value} is not in list")
def discard(self, value):
index = bisect_left(self._list, value)
if index < len(self._list) and self._list[index] == value:
self._list.pop(index)
if value == self._min or value == self._max:
self._min = self._list[0] if self._list else None
self._max = self._list[-1] if self._list else None
def __contains__(self, value):
"""値がリストに含まれているかを確認します"""
index = bisect_left(self._list, value)
return index < len(self._list) and self._list[index] == value
def __len__(self):
"""リストの長さを返します"""
return len(self._list)
def __getitem__(self, index):
"""指定したインデックスの値を取得します"""
return self._list[index]
def __delitem__(self, index):
value = self._list[index]
del self._list[index]
if value == self._min or value == self._max:
self._min = self._list[0] if self._list else None
self._max = self._list[-1] if self._list else None
def __iter__(self):
return iter(self._list)
def __repr__(self):
return f"SortedList({self._list})"
def bisect_left(self, value):
return bisect_left(self._list, value)
def bisect_right(self, value):
return bisect_right(self._list, value)
def index(self, value):
index = bisect_left(self._list, value)
if index < len(self._list) and self._list[index] == value:
return index
else:
raise ValueError(f"{value} is not in list")
def pop(self, index=-1):
value = self._list.pop(index)
if value == self._min or value == self._max:
self._min = self._list[0] if self._list else None
self._max = self._list[-1] if self._list else None
return value
def clear(self):
self._list.clear()
self._min = None
self._max = None
def extend(self, iterable):
for value in iterable:
self.add(value)
def update(self, iterable):
for value in iterable:
self.add(value)
def min(self):
if self._min is None:
raise ValueError("The list is empty")
return self._min
def max(self):
if self._max is None:
raise ValueError("The list is empty")
return self._max
def range(self, start, stop):
left = self.bisect_left(start)
right = self.bisect_left(stop)
return self._list[left:right]
def count(self, value):
return self.bisect_right(value) - self.bisect_left(value)
def index_range(self, start, stop):
left = self.bisect_left(start)
right = self.bisect_left(stop)
return range(left, right)
def find_kth(self, k):
if 0 <= k < len(self._list):
return self._list[k]
raise IndexError("Index out of range")
class SortedSet:
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a=[]):
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 = [], a
for x in b:
if not a or a[-1] != x:
a.append(x)
n = self.size = len(a)
num_bucket = int(ceil(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):
for i in self.a:
for j in i:
yield j
def __reversed__(self):
for i in reversed(self.a):
for j in reversed(i):
yield j
def __eq__(self, other):
return list(self) == list(other)
def __len__(self):
return self.size
def __repr__(self):
return "SortedSet" + str(self.a)
def __str__(self):
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x):
for i, a in enumerate(self.a):
if x <= a[-1]:
break
return (a, i, bisect_left(a, x))
def __contains__(self, x):
if self.size == 0:
return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def add(self, x):
if self.size == 0:
self.a = [[x]]
self.size = 1
return True
a, b, i = self._position(x)
if i != len(a) and a[i] == x:
return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b + 1] = [a[:mid], a[mid:]]
return True
def pop(self, a, b, i):
ans = a.pop(i)
self.size -= 1
if not a:
del self.a[b]
return ans
def discard(self, x):
if self.size == 0:
return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x:
return False
self._pop(a, b, i)
return True
def lt(self, x):
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x):
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x):
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x):
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i):
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 IndexError
def pop(self, i=-1):
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 IndexError
def index(self, x):
"""Count the number of elements < x."""
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x):
"""Count the number of elements <= x."""
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
# 転倒数
def inversion_number(input_str, reference):
def merge_sort_and_count(arr, temp, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
inv_count += merge_sort_and_count(arr, temp, left, mid)
inv_count += merge_sort_and_count(arr, temp, mid + 1, right)
inv_count += merge_and_count(arr, temp, left, mid, right)
return inv_count
def merge_and_count(arr, temp, left, mid, right):
i, j, k = left, mid + 1, left
inv_count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
inv_count += (mid - i + 1)
j += 1
k += 1
while i <= mid:
temp[k] = arr[i]
i += 1
k += 1
while j <= right:
temp[k] = arr[j]
j += 1
k += 1
for i in range(left, right + 1):
arr[i] = temp[i]
return inv_count
def calculate_inversions(arr):
temp = [0] * len(arr)
return merge_sort_and_count(arr, temp, 0, len(arr) - 1)
ref_order = {char: idx for idx, char in enumerate(reference)}
numeric_arr = [ref_order[char] for char in input_str if char in ref_order]
return calculate_inversions(numeric_arr)
if __name__ == "__main__":
main()