heh
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/inp.txt | 51 | ||||
| -rw-r--r-- | src/main.rs | 244 | ||||
| -rw-r--r-- | src/util.rs | 2 |
4 files changed, 127 insertions, 171 deletions
@@ -17,3 +17,4 @@ rustc-hash = { version = "2.1.0", features = ["nightly"] } lto = true codegen-units = 1 debug = true +# overflow-checks = true diff --git a/src/inp.txt b/src/inp.txt index d85f44e..27fabd8 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,50 +1 @@ -......................D....B...h.................. -..............................h................... -.............D...3.....X..................9....... -...........C........X....2.hB......v........b..... -....................................O............. -......u.....3.........p........................... -....u......................v....6................. -......................y..D.....Ov.2..............b -.....u..........X...........o........y............ -.........................y...B.f...........s...... -.7....................C.2.....Bsyp..........t...q. -.u.7...........X............................Oe..t. -...........V........3......6v.s........o....h....t -..E........L.................6..........o......9.. -........E......m.2.P.......O...9...8....b......... -..m..........3.......p..........M8................ -..1.....................K.p....................b.e -5...............L...........s.6..........S.M...... -....5..1.......E.........k.f.........M............ -.E..Y..V......l.......T...D.......9....Q.......... -..............................M................... -.....5....P................m...x..q......F......e. -................f...c......................x..F... -..V.C...........7.......a....o....8.........F..... -.......4....L.a..g..P.....8......Q....7d.......... -...1......4..a............k......t...d............ -..........V..........L....m........K....Q........S -..................1....k.....T.................... -..........l......a...............F................ -...........P...4.......l......x................... -.............c....g........T...................... -.....g............c...Q.......................S... -...............l..................A.d.T.U......... -..........................f...0.............d..... -..........G..................A............e.S...x. -.........Y.......q........g....K.................. -.....................q.H4...0.................j... -....................HA..............J............. -..Y..........................0...J.......j........ -.......................G.JA...................U... -.......5.......................................... -...........c..............G.........K............. -...............................G.................. -...........................0.j.................... -............................H.......k..........U.. -.........................H........................ -...................................Y....J......... -..................................j............... -.................................................. -.................................................. +1234649462611144453037831447782650154199904444418754393298142370965884849434468499632063186430373758261212246131269638862289982851199328376799168279795582765623726611801673866318448765341351918267349387295549369963783564627765549860288311622270652081331623303731394493363460181979845515387736964680867096758640946958543414346463705165538262546526685849633195972999203924932643729445403458944247195584523184579232961688214927991948214243724569175730583448284484356119292376162160636186866757817916638763541026228667687927489441312075616548246159384499118447986765804592228974577999418391558734571116287259842867478993963973808062272431173355709666156660615438628445554337897396311549911271914241808044129428431013727079642843477779848864247460711054698795421574452859693757769492604050285036418375879396146592482886487267502614288379508991976559251137771025201035238469498254706163746249664583352686888394389962528661423479377440882368727364852965181763743977304890783444241225367841815365615725373765909460767574983268599041248598298646246882925390333193758336614690606376229859977310952436193516243080142820736246797310504828128333142361961778395099418618769953521649497664886644853689964663439758873464151691988132858144867284958978962955808961183763417212216914927661207061698591644829513170478583448638771115917064791335345120696018156487311920831393667218862462828326378011177233463334414662167970933057637415104521428620171316583459805679855062302436487679508343616574352086477239525111898869755286883051481119247467698574572384843757198728737986321228982587952472519175188921187624567951396763394457786070692212852723244718893056488771519282915396222383964626402733754319192066624738216044945259379798266586195364878622624637701638932230139050603997272731932497316870102557444918199992601683572281921124755356293933564519462473215475729757934498602638582772881959496297271881909070486577451021976055772858475453196515216251924813398442755457684812611981656263259174656792437636372376213499942632258249978296218071178526497765836854834048629598968832652544893314561390614249526577284538916319273787723790619949495473517758716258234618353889749029227213746556982318987250869548462666124998253324231131502429378227848470323268162811262919415565497828579972282462311275737630184921206640284613845450135558338253976668476684759514421262733714843476976079144082858834376275451589896419311023486017685922427499385958861011112529695496899583601313766434263574866514284834451578432730477057327451819973418921194417879030654879945977556395855647794984824077896084248144248377475978169279597945104535933033538345154065962932153364492141267067547293921419856646889639117928768380492089575936888766423618211820459759164944608498513354769993392527363490525813214742786249129029618420443873127481937287728561146178342324935038274511517041666114561752702689702258497859619910792945773477433871324444431521732849908619134635748068931595575724763542359229429510973368217447511092804395326177727365989459398173125426738416694452553389206023877841571785555892491949632144373168895386557753619517684745967678725180291655383735568247954317411776264289229657393810344351517189194088589393165750472861165386595047291071456764214881794485175713274627283234523582343884305732478110125711297241746282361427905787166647974194156695297917744728986072776562623066144375358240927772158817551847216892308073898678128626418245344982127369572315531224268810964066259571984851415346908437426038381612816794929316252687267789263777858038875766339015559812293973867935504325429648571562995816605275619999957092856836307059515983613710179075979569868795191350653132838120722312976542663628482917108631329073222562457791926868149698254426946935451238694223453931387896798751239881935395854748492239272034854919384814888057947717382132434020691221934751479277277488381924725915627532635491417639815780893778169064391249299295961391242973897059321222431952669398107359364749247066963899412458493588475851618149811481738570622410741172283240882535228433612290827311518950568654755622818774595613899438405828503591817580378564226643395995909667539714934279146798901976844041843757348894968491751966983325803548156339127051266777943213196946443685147924101736771537126616867472648750915937969376713819404443987456834538499725447029553244467479941638276481321773611758618017954012345236262287882629661651184360217037388620264740406945544570961969439324827723389371576177441792524882783425205310642840393449536313181829908155322642906538923327183337566748261638651153339081288688754570832098771166148667195983395217796366324354117432877437946495139245484548619623121939221279817485372067452674324453976887546435631418382763557184396342836454571423905055892587918887749615509794173638669092345511447263956156414193204688831184714665889259451439259332311845368943513782263123753777696231694194205495704959922723863880432298413636168381616078573062891598315112918219446554845576533892998692325370594474488539426448814429319426521784182769355925546782632073126961818820906590487395948846166059333927649267297696564965543543947669578590562797409937638871106839913865254341245622412121471859998754578132908841667541892012245858521478756969929316422343942158112797752033183928934658142924752050331176202193334788576912574998658539251115539850283720677650854320576562811551173174578775833328416399162054304788347188291756761439376174388945361219433952335731331821396862218232571525612441251632111848598489974740278692731094122916338949484827142750121531675742965367664641411215414977764115388531647726882037293924637143339974272693733161329484435818123411792184988060974583376955921262599899798211923411428461503498359139894628353480323514903211371414868338889037113959618044305359691573337691109965243588528174194180469092705227532616895293628795765668614773534262141057283252953280472752816169227820629710137797844689886847471636687470336478161230636994287399152051504784202946479867156397644210979880186022878788359828251638383974102549761783143734946341195567965634439759146574513251144937969611361249537917121372414247972591798856129814212926346780449724205525637578952290971474136849879738496771728812252071152898776643786732575294105085665738568074607091191283124971896828783299216714398933508987444845687236538244919298383420637051455094528433138730494627177864361713888977647594843636863317479195475629241971697915947726187830636564114098823729843453743461176752844733713545946539141275604894958278308574593424912829229060391133968790787239888747321781532263733749869585143690721342984578234314138614219443741964162918192511776832307690816985214682826410429113433787575317177081795481623259194420753679905138459037544569162935785886994669122850597696389272946729461351613281911162944812417039904767335394611377936922968695541632214837766439787678309195835518662020544561175329341966194572391843719670973031909794252461657162466559118389525946683914729646204585238287215015856124793234672117822717976787185988389052378159892627129540797921702264906257978611257662924043538394716288231727801998187187227545435152579280644629885225697915598946894373494552184543586517474216755926346294581650628813909257673552914519272495581035816539773930958365491741897244555191289966856363614457944142104028159215274555547615795612282959706667958517156783288251367492826848161218955073602427427613866547424122779329827650419258475355528732104767154285734878232072113972557231629537666041754763208932564176315965371571383181346549876030691828952495268968552072988533919895554730738974972372786236634325509460741682123451746919691525537131894351712995427360325069963468615981429463369178879194958216319775496929998671128072275162382737436456495646683993224992449941366156151414324975676576872522428391202716503172565829321488954682824062501920887040764724758196973087523652269198535721157255732641526649609085347729336341408962914068474252322526895938397461729641429980421181955991429017225932178199739658878987489079502213396990782166303645391029191076297572799271438728949662124867565670859790248322321236718646925336247691113181901650314485848572184556276915306733817135286642638378951375485373189842268454101510974096511347766786745747794875723724881223172731475438554113499294969230499896345364273670256198206361788627735155643452404863439889102496402539898169831597788727256514363910936734802416426149697927797183906033235567413213114286602774426463944329826735551766127960729197555261383539342258852893509229687442528542892468292876505980844924717071681184235250353062141872606939592119818063699734998822637498327818971632322191142252765521191882302148619947798440996859987270864334885820529015606841758773115545802669996133895872649425269641769212338078713611157794446098135242912651414750938184643032408516186418218310825119971251884154566626451040465935791155267664965212982379967351582094996554946459503559976317356932677133292693914278258419209666809193139471362474128491715612842727186119275974722714538464947322932735687149316356125722776428705977516372408861301634138532147866826450181780358498121536279382774438451183535084522947251888472178724244728889782974787079372974867189866494314499638174957259498495953236455076783826294773845029255446696373885569187688314133635866751826572757791714719332648826835032975434899567438180539277412871625177258362716798569982193080853747635666229795587060815759883462799662999279281879889544447846998895121317163697327374623366365494312795131669887078122750964953833171135613156691477326906946915144503239794448344065795016443772969723225530602183164373388284243658719982359081337784544756152882542982248296171996642513454369528658681478664696491045608030172999575312369037303249921484625747173199419882954733117690704926834630584514198542204474193666742247122171655737153171159027681876466734656327278732217893868563149033231793843566344620958028773480981963599535348195704851936829898797882956834618671828864326738830352590847228572746184857143063699191381176809359302352278667589233728977142373127065492574875940238282782968328121455963321288107435401882629725448916276575713760423065787750889229626255811896697863305261308256591062193592365073177790111316928237336250615778303925497222349815447666623691882856521963422160416526905590205654818379481079832676895893516482919098764532765884754140636867697828879918743336295180363016636236554343569157783196458934494242767416427230112632265114358942258939467212335456246142915087939322721885507959525338944694102064423525345877641263544618974894262130974888835426839893144845124061466953249766799754867161993468646637226936342238463268159027531420438573125422181067839858894584651032483726128792645244444587857165471714164430522077509558906410145557497776706768664945661987284613938937966858361365958432955693463573964610831827659182288944736688257279732159219389395343654886953252935763528931501753883851419288867394324422949986212483187026529690533244118174472897696529444842312748845940393277102367571891231253993883793538532382138160465617573716926448591122659290612496583451943215966591536875995057382768169219819846513334183940952663237176554280561472164358123554759949165632443698949857299892249787861662462741789978508818568295126549621593912961256298688249657995496325177665344470129177795561631322891270958612808375683533445653922751355556527997399410403045505310227740132655461049557455757716918371662021522040264347781289236560314910729567774042917294466026232041338426268356414666696685618831128947696830192726342727659063167573358598463282853362891416137852368249578331165749498863177755377179271688145726904738738775913328718248907524647034611183528360986383988789146143131221465233244463795429165699288721628353225078899212116263685478256572762427535699363946563736571660761916816356501740772287761381648478644521443563953891156320236488296157463385186992589615191765352938737714735186567044283819446960576428733969595551489270233391965248743919826934397334724083291232757360766811988674258762595131309434533034173773362060107866462021178362333612636665775088122528546161939944881556513613185432793742955868622916704261788240453061539847774927648113792187652621182946526129438440793058323497149197348339101668237436337863854262345870426293999529441396908147223135289276646634234359848169247211307221485513834587612520118381491989233378338592493584912437519388862098874538247876102371134692177497956989315568485873834869526884729692873984257737156350396433321469694823324639117237895583489785306476695336677490871019704876455928998481724442655661912947346891752622133978196185707040762820189760556431461318739674241357759961726398635792176215833577217385765520798268513850858528855617541178359118456771205355446886836279396677368214701968834319616520362811555127225924941878204865772895662856835950307483968248842148769435637545271491339887999517271334113166313630674335913788856855806171113579143711281382672434113294853827828534435910284883729080247711887487164672196612413356974530834818796014636870735431338419854590689778431376714961729462727565822830141467898762247348731220354284508736114448419919898655912358313893774883851156663629482347537228236931837184806621583425239473677899963370735839439569395381139294651014735147997144635199955631313270823235651767588848987632989334499857191126888656516492237592582872312229976650429432298789223289912459172578827517519949514979974990467568877685375264826470636664785878951492886848357043172833183081404537626279577045938921671219761557124310816435418856762936577210623382746676916878247231224034871663999696886967133780556811351178734157535963948558179225146834193780497919211074392022992876615823299183601156314748926642563679601270186612718133977063984198876161315871835940178889765872903751747680959637952696449848408760317099583025516486831191451168144625261697663322682335545386919314146736213874669877626689672687273398416466542662555252404142422160213942856844858580167073876174381893288268555398628470281294357633363187567269267741511370722017779859164720978515401819733127882032321824145143839353597274937062166718657982399622995777799946162620655525845835197711708389815790283178956622318615846329219011269748755869174665584877361468845834785872181772722488938288369952865678982321607894811523912426637732991352455290436411158642467661306110494589431756694615451643558055307742745264394064339637876076514161588480401656364618803990367995924896802765811954757273416269443881528439391962809838452561613433259520658643544884283962148841216423188095878698479572984182929124606971252436494493396324826828328050125535707665152524608649662257923840701526101567644743698244788177168514294855721356454441862763105515877483483047109253312650946425686237743272179936476617735219747363125154506771613181226797935789744560603274682072817876849196714014175430916017449393256028246734647851749047737216923496449459375198966656459629518666541152411522299519399950714755453072653978469616276763553231567998525816523439933397942562407253535193488181371756865421388568738590619895473958886776651694198087245641962766149747113729378614667877332429678760529138617060528470136948299577573791442662428859329450301916191415387879356227407914897057246745598788784385925091691662603624309916752343244843559870136826526668709967119934242745313312996195717019405045451143494133406924893827683741484553653797274527782614751561694783748066621491723567734015325941863235113821774975135398589041732918744425248956671348739984473456229660894661881180798487492442355224141669948823541914702862519339491198616420589411819762854248287363651523474376125238955392374548799765606877969272371236322373997923823733791374477793866565616131966191464879546239796264141136829092733784333977364344637220715568406513561667195051693879729250583313941694556527355741388164249844335018789312968081845692312278666363129769793243809226722986756136245657467888688174748239951587781910662791286030658070255984926769297632545321994756844250993032504883929095248719454066973246632247191651758056286838496854479287678743257811504685112084706647292338754337277680831295332166431256422450944365476747722688973461594552702226236026606656645682856850201670227472185119594651653039334072279791545032432442351386167834705255839913681383944649128446253871558915957727591054771714429050591119862444847144362618963436523325168690619540925395437220113839909267461254147882567147495696433972571075698856348171649160267532445889259123177293832393457959444257683031256147654256656319999192467120772791396339541923417072721412166830345334572675829561584978563176125119801296341430105963462968121971903755649119986743184826135571503559785329318654244354868842882628121353689619967775868242723455733042354311234886555272833251834878259138306481282664453636599536641947672611306039465257701732513637334057746218481224225575591791938846519474145560263562211251345395753813104593753282302225127062694692527091751575213316922254709813155548514460916072991862183496644915781565588693502995942547263746493876994058836364328369575937417513166234467243711695702034205977161553984134802280667098478659311989577538605085118499415692211878286962769624317639352398144786248593466090852322834689443045892664171598547527783987649511662934577942818534687091202090359081719620963651506483374545518162837725229791862632524088968372667333562269349522312751614283506136241330364855821169676038876343979972326989399865659027983985393452167011342295653565549087271335991189247939792418731983974292157558956887904184441770216671569549842986576116978341732428589216369240805626466573946728211644993198416290771279369198655412325548492213891558463834766515199316919680464312436863779818668765831657404628165417407488879422677445221764626620152366489926501837422884676961579595264455921977389268881777436934918110956012142067327319194011563863181694547988634690532986515073523693159657627859683458126049267778746099212990832262965836716163395489859529833597948521986876251471734834175423287055888814796138158981792198951645445140381591639696609396437054191460468872676287319598179428831762801673211385146530472217582533116182306925195029539390372767348531207741644991545568122282447059506581387748959919127355448017203477176552781834608249783580505952197197415440687665185943141831304030584890958268335753231655409471827570622932162266653333407188899611899021309334637063475630428739644086751585889065724775945232505762671574393131994911251964739814483282775834452797226935877529985177977655572849159871359626277732611224281416445422365460497683264160674370872225557331794518124964761787661393608339113973908420773046324686855742755747794982882252828141758130627448798492994445769050464366794320751254802993871032344188855770809649997897252845501528345195724088863511426847118247292264265740106190425237835622891865463565339999994281924835644165897688643958408437921896223212698819508186521292973772585522214355435313583922932368928767844054433317909321136593809767661759682612287462563774535580649180212950906248877326588097774848588450421294158155127055586345779028878816387336185921401484348858359515596935904860944621418269664529631782115289702183387751497943252993129558258450985384536396924869422058637542397685159314406765458578114631466690651932803740611233515540878886189987522582256441768965748425342040203013904454151669383948159867478248704761905329621586482058868473929398631291319013217947907082668362507280667291236434236614849557846356519821111338216849343330376961644273161037126785468422663714478098599769907158821060567740465450519324187775693753119867101221482354416753919174538341786852251013787167195433238619794149653913533268176678826064573386119072352243313435124941352796298520228411189814179052975270304327429018455813733818285211471177834814613063927063383878719949689196594491532718936418786563983423611085975595449375746289644245878540886557332155594235123711585466313388811282119241513091103492947917864765599815754752635525978359199966328540327360697172656186873575401867895472239956286383729518302830767224688143148210767093333761312077897 diff --git a/src/main.rs b/src/main.rs index 01f47fa..300e091 100644 --- a/src/main.rs +++ b/src/main.rs @@ -8,6 +8,7 @@ incomplete_features )] #![feature( + iter_repeat_n, slice_swap_unchecked, generic_const_exprs, iter_array_chunks, @@ -18,6 +19,7 @@ let_chains, anonymous_lifetime_in_impl_trait, array_windows, + vec_into_raw_parts, try_blocks, slice_take, portable_simd, @@ -32,138 +34,140 @@ pub mod util; pub use util::prelude::*; const SIZE: usize = 50; -fn split(x: usize) -> (u8, u8) { - ((x / (SIZE + 1)) as u8, (x % (SIZE + 1)) as u8) -} + #[no_mangle] -pub fn run(i: &str) -> impl Display { +pub fn p2(i: &str) -> impl Display { + #[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord)] + enum Item { + File(usize, u8), + No, + Space, + Spaces(u8), + } + #[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord)] + enum SimplifiedItem { + File(usize), + Space, + } let i = i.as_bytes(); - let mut big: [[(u8, u8); 4]; 123] = [[(0, 0); 4]; 123]; - let mut lengths = [0; 123]; - for (row_, i) in unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() } + let mut files = 0; + let mut map = i .iter() - .ι::<u8>() - { - let row = u8x64::load_or_default(row_); - let mut row = row.simd_ne(Simd::splat(b'.')).to_bitmask() & ((1 << 50) - 1); - while row != 0 { - let x = row.trailing_zeros(); - row &= !(1 << x); - let &el = &row_[x as usize]; - let l = unsafe { lengths.get_unchecked_mut(el as usize) }; - C! { big[el as usize][*l] = (i, x as u8) }; - *l += 1; - } - } - let mut anti = [0u64; SIZE]; - for char in (b'A'..=b'Z').chain(b'a'..=b'z').chain(b'0'..=b'9') { - // let memchr = memchr::Memchr::new(char, i); - // let wat = memchr.map(split).collect_vec(); - let all = unsafe { - big.get_unchecked(char as usize) - .get_unchecked(..*lengths.get_unchecked(char as usize)) - }; - let mut anti = |(x1, y1), (x2, y2)| { - let mut x3 = x2 + (x2 - x1); - let mut y3 = y2 + (y2 - y1); - *C! { &mut anti[y2 as usize] } |= 1 << x2 as u64; - while (x3 < SIZE as u8) & (y3 < SIZE as u8) { - anti[y3 as usize] |= 1 << x3 as u64; - x3 += x2 - x1; - y3 += y2 - y1; + .ι::<usize>() + .flat_map(|(x, i)| { + if *x == b'\n' { + return vec![]; } - }; - match all { - &[] => continue, - &[a, b, c, d] => { - let mut one = |i, j| { - anti(i, j); - anti(j, i); - }; - one(b, a); - one(c, a); - one(c, b); - one(d, a); - one(d, b); - one(d, c); + if i % 2 == 1 { + vec![Item::Space; (*x - b'0') as usize] + } else { + files += 1; + vec![Item::File(i / 2, *x - b'0')] } - &[a, b, c] => { - let mut one = |i: (u8, u8), j: (u8, u8)| { - anti(i, j); - anti(j, i); - }; - one(b, a); - one(c, a); - one(c, b); + }) + .collect_vec(); + for i in (0..files).rev() { + let (i, _, &size) = map + .iter() + .enumerate() + .rev() + .find_map(|(j, x)| match x { + Item::File(a, n) => (*a == i).then_some((j, a, n)), + _ => None, + }) + .unwrap(); + + let empty = map + .iter() + .ι::<usize>() + .group_by(|&(&x, _)| x == Item::Space) + .into_iter() + .filter(|x| x.0) + .map(|(_, mut x)| { + let (_, i) = x.Δ(); + let n = x.count() + 1; + (i, n) + }) + .find(|&(_, x)| x >= size as usize) + .map(|(x, _)| x); + + if let Some(empty) = empty + && empty < i + { + let f = &mut map[i]; + map[empty as usize] = std::mem::replace(f, Item::Spaces(size)); + for elem in 1..size { + map[empty + elem as usize] = Item::No; } - _ => shucks!(), } + // #[cfg(debug_assertions)] + // println!( + // "{}", + // map.iter() + // .flat_map(|&x| match x { + // Item::File(id, n) => std::iter::repeat_n(SimplifiedItem::File(id), n as usize), + // Item::Space => std::iter::repeat_n(SimplifiedItem::Space, 1), + // Item::Spaces(n) => std::iter::repeat_n(SimplifiedItem::Space, n as usize), + // Item::No => std::iter::repeat_n(SimplifiedItem::Space, 0), + // }) + // .map(|x| { + // match x { + // SimplifiedItem::File(i) => format!("{i}"), + // SimplifiedItem::Space => format!("."), + // } + // }) + // .collect::<String>() + // ); } - anti.into_iter().map(u64::count_ones).sum::<u32>() + map.into_iter() + .flat_map(|x| match x { + Item::File(id, n) => std::iter::repeat_n(SimplifiedItem::File(id), n as usize), + Item::Space => std::iter::repeat_n(SimplifiedItem::Space, 1), + Item::Spaces(n) => std::iter::repeat_n(SimplifiedItem::Space, n as usize), + Item::No => std::iter::repeat_n(SimplifiedItem::Space, 0), + }) + .ι::<usize>() + .filter_map(|(x, i)| match x { + SimplifiedItem::File(x) => Some((x, i)), + SimplifiedItem::Space => None, + }) + .map(|(id, i)| id * i) + .sum::<usize>() + // 0 } -use std::simd::prelude::*; + #[no_mangle] -pub fn p1(i: &str) -> u32 { - let mut big: [[(u8, u8); 4]; 123] = [[(0, 0); 4]; 123]; - let mut lengths = [0; 123]; - let i = i.as_bytes(); - for (row_, i) in unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() } +pub fn run(i: &str) -> impl Display { + let i = i.as_bytes().trim_ascii_end(); + const SPACE: u16 = u16::MAX; + let map = i .iter() - .ι::<u8>() - { - let row = u8x64::load_or_default(row_); - let mut row = row.simd_ne(Simd::splat(b'.')).to_bitmask() & ((1 << 50) - 1); - while row != 0 { - let x = row.trailing_zeros(); - row &= !(1 << x); - let &el = &row_[x as usize]; - let l = unsafe { lengths.get_unchecked_mut(el as usize) }; - C! { big[el as usize][*l] = (i, x as u8) }; - *l += 1; + .ι::<u16>() + .flat_map(|(x, i)| { + let times = (*x - b'0') as usize; + std::iter::repeat_n(if i % 2 == 1 { SPACE } else { i / 2 }, times) + }) + .collect_vec(); + let (map, len, _) = map.into_raw_parts(); + let eight_bit = unsafe { std::slice::from_raw_parts(map as *const u8, len * 2) }; + let mut emptys = memchr::memmem::find_iter(eight_bit, &[0xff; 2]).map(|x| x / 2); + for i in (0..len).rev() { + if unsafe { *map.add(i) == SPACE } { + continue; } - } - let mut anti = [0u64; SIZE]; - for char in (b'A'..=b'Z').chain(b'a'..=b'z').chain(b'0'..=b'9') { - // let memchr = memchr::Memchr::new(char, i); - // let wat = memchr.map(split).collect_vec(); - let all = unsafe { - big.get_unchecked(char as usize) - .get_unchecked(..*lengths.get_unchecked(char as usize)) - }; - // assert_eq!(wat, all); - let mut anti = |(x1, y1), (x2, y2): (u8, u8)| { - let x3 = x2.wrapping_add(x2.wrapping_sub(x1)); - let y3 = y2.wrapping_add(y2.wrapping_sub(y1)); - if (x3 < SIZE as u8) & (y3 < SIZE as u8) { - anti[y3 as usize] |= 1 << x3 as u64; - } - }; - match all.len() { - 0 => continue, - 4 => { - for i in 0..4 { - for j in 0..i { - let i = all[i]; - let j = all[j]; - anti(i, j); - anti(j, i); - } - } - } - 3 => { - for i in 0..3 { - for j in 0..i { - let i = all[i]; - let j = all[j]; - anti(i, j); - anti(j, i); - } - } - } - _ => shucks!(), + let empty = emptys.Δ(); + if empty > i { + break; } + unsafe { map.add(empty).swap(map.add(i)) }; } - anti.into_iter().map(u64::count_ones).sum::<u32>() + unsafe { std::slice::from_raw_parts(map, memchr::memmem::find(eight_bit, &[0xff; 2]).ψ() / 2) } + .iter() + .copied() + .ι::<usize>() + .map(|(id, i)| id as usize * i) + .sum::<usize>() + // 0 } fn main() { @@ -174,9 +178,9 @@ fn main() { // s.push_str(i); // } // std::fs::write("src/inp.txt", s); - // println!("{}", p2(i)); + println!("{}", p2(i)); println!("{}", run(i)); - println!("{}", p1(i)); + // println!("{}", p1(i)); } #[bench] diff --git a/src/util.rs b/src/util.rs index 5905ee6..099cd6a 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1146,7 +1146,7 @@ pub fn even(x: &usize) -> bool { impl<T, I: Iterator<Item = T>> GreekTools<T> for I { #[cfg_attr(debug_assertions, track_caller)] fn Δ(&mut self) -> T { - self.next().α() + self.next().ψ() } fn ν<const N: usize>(&mut self, into: &mut [T; N]) -> usize { |