Task: | Planeetat |
Sender: | Hennkka |
Submission time: | 2020-09-27 15:32:07 +0300 |
Language: | Rust |
Status: | READY |
Result: | 49 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 24 |
#2 | ACCEPTED | 25 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 2, 3 | details |
#12 | ACCEPTED | 0.06 s | 2, 3 | details |
#13 | ACCEPTED | 0.86 s | 2, 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
#16 | TIME LIMIT EXCEEDED | -- | 3 | details |
#17 | TIME LIMIT EXCEEDED | -- | 3 | details |
#18 | TIME LIMIT EXCEEDED | -- | 3 | details |
#19 | TIME LIMIT EXCEEDED | -- | 3 | details |
#20 | TIME LIMIT EXCEEDED | -- | 3 | details |
#21 | TIME LIMIT EXCEEDED | -- | 3 | details |
#22 | TIME LIMIT EXCEEDED | -- | 3 | details |
#23 | TIME LIMIT EXCEEDED | -- | 3 | details |
#24 | TIME LIMIT EXCEEDED | -- | 3 | details |
#25 | TIME LIMIT EXCEEDED | -- | 3 | details |
Compiler report
warning: unused import: `std::collections::BinaryHeap` --> input/code.rs:3:5 | 3 | use std::collections::BinaryHeap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused variable: `n` --> input/code.rs:301:13 | 301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) { | ^ help: consider prefixing with an underscore: `_n` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `k` --> input/code.rs:301:23 | 301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) { | ^ help: consider prefixing with an underscore: `_k` warning: unused variable: `max_s` --> input/code.rs:301:33 | 301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) { | ^^^^^ help: consider prefixing with an unders...
Code
use std::cmp::Reverse;use std::collections::BTreeMap;use std::collections::BinaryHeap;use std::io::BufRead;const MOD: usize = 1_000_000_007;fn print_iter<I: Iterator>(iter: I)where<I as Iterator>::Item: std::fmt::Display,{let mut iter = iter;if let Some(v) = iter.next() {print!("{}", v);for v in iter {print!(" {}", v);}}println!();}struct UnionFind {links: Vec<usize>,}impl UnionFind {pub fn new(n: usize) -> Self {Self {links: (0..n).collect(),}}pub fn find(&mut self, n: usize) -> usize {if self.links[n] == n {n} else {self.links[n] = self.find(self.links[n]);self.links[n]}}pub fn union(&mut self, a: usize, b: usize) {let a = self.find(a);let b = self.find(b);self.links[a] = b;}}fn modpow(b: usize, e: usize) -> usize {if e == 0 {1} else if e % 2 == 0 {let p = modpow(b, e / 2);(p * p) % MOD} else {(b * modpow(b, e - 1)) % MOD}}fn modfac(n: usize) -> usize {if n == 0 {1} else {(n * modfac(n - 1)) % MOD}}fn modbin(k: usize, n: usize) -> usize {(modfac(n) * modpow((modfac(k) * modfac(n - k)) % MOD, MOD - 2)) % MOD}static mut stats: Option<BTreeMap<(usize, usize, usize), usize>> = None;fn super_binomial(k: usize, max_s: usize, s_count: usize) -> usize {assert!(max_s >= 1);std::thread_local! {static mem: std::cell::RefCell<BTreeMap<(usize, usize, usize), usize>> = std::cell::RefCell::new(BTreeMap::new());}let saved = mem.with(|m| m.borrow().get(&(k, max_s, s_count)).copied());if let Some(saved) = saved {saved} else {if k == 0 {return 1;}let mut sum = 0;// Try all possible sizes for the next subsetfor s in 1..=max_s {if k < s {break;}let new_s_count = if s == max_s { s_count + 1 } else { 1 };sum += (super_binomial(k - s, // ks, // max_snew_s_count, // s_count) * component_count(s))% MOD* modpow(modfac(s) * new_s_count, MOD - 2);sum %= MOD;}mem.with(|m| m.borrow_mut().insert((k, max_s, s_count), sum));sum}}/// Compute the number of ways in which n planets can belong to 1 componentfn component_count(n: usize) -> usize {// These take a couple of minutes to compute, so just return cached valueslet cache = vec![0, 1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 660215659, 920608908, 836504326,639554500, 466620985, 872046927, 308717370, 502812808, 646301526, 985602096, 8033007,199948617, 265123234, 963316760, 97012001, 520509077, 963089188, 609109590, 475681640,268714573, 138142320, 659323185, 432287876, 833911481, 580044808, 724047794, 752488773,369844336, 411404305, 966444867, 966304277, 670002988, 356672355, 499497440, 858083915,849461059, 699627096, 696125320, 569657991, 589455080, 637699856, 159331976, 253230028,126065421, 190780359, 657860743, 35914725, 627548423, 786042624, 88732365, 595484631,907204844, 310896156, 654434332, 999859588, 891860619, 760802640, 321240817, 284705446,581193655, 540500946, 828699763, 86377965, 299422367, 636989116, 804687707, 341628824,969661800, 493359322, 269113227, 2788545, 136045625, 319856162, 734688215, 933443980,548820306, 844116817, 949670148, 893770986, 562714601, 464787503, 785661356, 27520011,33434941, 651969158, 596069751, 447474780, 454137267, 430168215, 427270537, 894456323,432736565, 541462563, 580395437, 926815786, 263023838, 779713525, 129353767, 254646934,327058306, 318061585, 873404148, 546897006, 256895690, 845805366, 521993981, 151412543,452233370, 169107595, 352810726, 932989581, 82660203, 144142246, 7983114, 841762719,398368184, 36362596, 5939420, 621718875, 180998347, 89322205, 709123956, 45239813,623512817, 592243835, 375742205, 13182108, 741093354, 954650126, 632161601, 323889231,855586538, 576541114, 402077493, 420399764, 23768284, 168259101, 986206037, 639024795,827219225, 972138947, 118660280, 935496148, 260619316, 568756388, 474316106, 90646046,327256160, 906940925, 61315684, 100123479, 904812330, 341615294, 269531078, 100088684,608203198, 84183940, 718793427, 269849284, 338624606, 60645067, 579226929, 140045143,723080187, 393278301, 585228375, 59206357, 101985982, 672040685, 139906388, 744500615,662412691, 158778780, 73399837, 332041241, 281105866, 957970313, 29966196, 815538417,292300246, 570909748, 771503216, 214191103, 101730853, 63227600, 308932805, 811045900,464333632, 357992660, 77607798, 507287768, 341677483, 72934014, 46989119, 114936355,602267494, 906589693, 582034332, 895922440, 156857108, 618036646, 157634170, 761405010,817859847, 467337486, 632543264, 517776051, 994834897, 687965083, 457907638, 825497422,243467865, 14399121, 407258784, 98570234, 748959757, 297443300, 406918679, 871245292,252946284, 452320327, 942393032, 318555470, 766642481, 981668534, 724552884, 301298708,142719827, 453758144, 985372383, 718141077, 18615310, 590242901, 715391284, 471018736,571254190, 833968271, 832120869, 945980567, 722309937, 54672675, 115490430, 187087627,626363638, 686555146, 318156532, 972513131, 167214298, 90260614, 306880672, 32986840,478943540, 672206708, 393818545, 416131966, 388360852, 956022816, 146560536, 392214273,327393841, 526526895, 175253967, 352945422, 306638803, 941328742, 230321990, 570405207,35763767, 385325705, 457471115, 680333391, 913022330, 507476085, 625156383, 460862378,719762476, 612136402, 543142329, 910689236, 864620931, 94770086, 124023110, 936801504,312536722, 840866722, 550990595, 847033780, 9264261, 210329044, 369392790, 722084766,940376498, 107971898, 858413915, 472976473, 311774094, 267458901, 145925718, 338817999,630914080, 579431167, 386296719, 138838078, 585741448, 847119734, 643211690, 268683825,351931792, 735656552, 8097207, 868683252, 134721277, 751435055, 835490594, 768101286,361829871, 395204061, 571729313, 121053572, 334933401, 823546703, 791822392, 196085636,914631844, 921218256, 269969740, 960245594, 308426560, 50228312, 203517952, 816105383,292189633, 32732523, 666262122, 437188886, 72215308, 918176539, 415978508, 85324969,769013382, 647852341, 689378978, 613167392, 340915335, 831071843, 565517411, 255908828,91838622, 605127507, 57150948, 686992820, 685954022, 342552285, 849812665, 260415783,694407779, 131097970, 232078836, 790843917, 602509046, 136064185, 155679521, 958411398,943708467, 206313402, 358630277, 411970955, 489455840, 988325815, 978309818, 166561041,394433021, 617840127, 693970966, 995469520, 143162639, 766345048, 552437316, 141371172,32069679, 516006699, 884187788, 608358064, 219163692, 387670703, 175148085, 17199999,180488480, 660440926, 864052274, 765128850, 483638267, 499688410, 640750115, 524434952,827157815, 514841947, 891119953, 537621015, 892118064, 928120221, 364674640, 992761107,724302220, 924628854, 760255237, 179981576, 235556227, 244177714, 854964962, 259182566,77503409, 507837049, 779838104, 423943877, 886744385, 958705993, 455048970, 824356123,713721861, 331904766, 623348072, 897891320, 902610163, 946917405, 630933809, 683877164,640836005, 535209373, 166585714, 161480461, 455967117, 252642116, 897912756, 319743887,916746661, 702589733, 778455519, 547659731, 289013415, 557947707, 955879877, 505371826,707573819, 803154268, 969112213, 221690942, 226656978, 735346391, 982277351, 592777469,447310232, 172403391, 748268363, 696182473, 52336674, 694374706, 788244971, 937988296,79919141, 145294051, 52674283, 265392050, 996188166, 381465305, 372742716, 485059689,315704434, 844900882, 764763714, 551996787, 961793773, 365663110, 538922989, 601146238,25707931, 555697561, 878705277, 319447511, 428853013, 742394955, 53270809, 647847019,542010010, 434050460, 439016902, 973744116, 662776175, 977629798, 900768919, 129073991,76026409, 498192056, 215123369, 777607783, 826637623, 435940858, 632532526, 979699864,273969950, 918223569, 797914606, 282218800, 216770185, 381331949, 326172660, 120803564,853670387, 682492038, 972664354, 284139447, 315944240, 800436189, 46026170, 412249526,683709489, 832181317, 394745079, 28240146, 163080658, 90324747, 780658649, 40050836,753363258, 490090701, 507159728, 175535065, 880542882, 601405007, 875042173, 622572015,624703488, 609933868, 870319039, 519399753, 237139139, 171461911, 722145611, 176534686,748791413, 777888894, 189895535, 776214576, 62907885, 838377878, 93453694, 917533875,810336630, 609416452, 888415765, 393387753, 513394863, 223454100, 439177115, 473459974,622286412, 444809364, 970826379, 277126519, 793591686, 566696364, 524560088, 518622823,740934331, 615919709, 233608104, 444215291, 445025848, 856961685, 923580922, 185212905,392675418, 727388601, 865839801, 76975614, 920825987, 676444158, 68254115, 754592218,324465365, 841768008, 273959910, 326575287, 547731766, 319188450, 611633037, 901608514,588206840, 732761621, 715062417, 742160893, 339850593, 508303398, 393630144, 829399774,404455930, 437595436, 84921880, 613757541, 683956864, 584483785, 227026419, 418559713,401523829, 185477490, 249706231, 327552152, 770760761, 378607522, 394710363, 763322048,628614375, 939574117, 900466080, 643974820, 674683595, 842164179, 895649271, 202668486,109169255, 296830144, 371897295, 625604906, 869773593, 833554505, 306574822, 818243912,654193167, 960565833, 804819530, 647238123, 885855615, 215870028, 964455102, 92443932,559430472, 23511463, 264092633, 260000328, 79622179, 474381606, 554791439, 330903508,511020268, 932195757, 352156109, 733558674, 294113392, 142386392, 964997788, 528074716,830312898, 163010932, 863889744, 102244077, 676493916, 912089702, 24225168, 465021266,603765333, 103120244, 784797374, 893623207, 595340442, 425658649, 291577723, 670989044,79022991, 21873737, 425688347, 89846397, 488428951, 746805572, 248666732, 241174360,684601776, 236729218, 422757346, 364668703, 293549644, 380351742, 772661211, 276677051,501793049, 880460037, 883830717, 379239787, 307979260, 751943962, 510752702, 744824767,442457467, 362155826, 489422317, 536111619, 914573030, 747095783, 884906140, 884441968,733653555, 146854917, 937116871, 163855877, 779645110, 709087432, 19492549, 147701829,364984477, 953983272, 567675621, 706105104, 157113580, 513338758, 653488931, 868545818,937865416, 255354491, 424337212, 586865979, 617557895, 111291906, 81586380, 569226029,722531365, 497424224, 114733014, 797099698, 225894714, 90394372, 447007271, 10245498,898128017, 766053818, 530349910, 882939708, 729004111, 108441817, 872910612, 705372057,995052453, 130708566, 269715702, 758342226, 348077669, 325709455, 866705688, 910469462,386447238, 115474755, 759928927, 272731632, 965099577, 72891374, 77737598, 502245864,685947101, 826847537, 819513705, 190633932, 555472343, 88760039, 762976966, 402514248,839207200, 779254057, 705559546, 562644196, 350626583, 9509184, 126888328, 152195603,132081101, 676239633, 458726032, 589898338, 148686953, 885348268, 801459787, 139572747,673185038, 991695943, 862630555, 366760847, 80076634, 966502459, 821571988, 21572279,721384935, 734870723, 218142410, 199368873, 604049970, 825401160, 507527461, 513100735,948791033, 203154030, 58041031, 640367423, 318384869, 77570129, 824194966, 825656956,77368019, 11306670, 106866672, 492360111, 943360649, 406075975, 779083698, 310454415,342169482, 803327115, 807386468, 255782051, 440244031, 950122691, 232360024, 101541391,865866499, 288404715, 96301762, 746211745, 673942807, 915823587, 417570436, 598672851,160322947, 244425439, 789934672, 618584932, 214979299, 860921706, 107319155, 316165313,965981656, 871166204, 841585452, 464957002, 668310812, 444833369, 849040138, 686345409,528113576, 983914180, 541311807, 848006220, 419529610, 171694617, 659806304, 279589304,208134673, 783769758, 974670184, 355188677, 141562686, 300791432, 842665724, 650736657,422159400, 50567611, 947382007, 87673516, 55967662, 261441709, 661131710, 755028429,841985974, 201632612, 945517170, 164980904, 817773860, 82055469, 445290969, 706944415,725447477, 664136292, 389817602, 780086779, 622797299, 148415442, 5708337, 666556057,224133097, 366882575, 914194185, 882014633, 978575769, 90170576, 471762897, 542460155,514096839, 701614974, 60312755, 917231767, 964520213, 358490848, 81057698, 247832532,341219882, 100102824, 341934238, 114183004, 209145178, 923964885, 435124520, 365469193,120384141, 56549158, 152602509, 361071024, 978731849, 532938250, 594199322, 752806852,456440644, 567440735, 988054619, 827866096, 699153707, 608834898, 362641723, 328571157,127445368, 597814206, 973349517, 892205335, 417582204, 988281451, 517534077, 352254670,336896544, 306733391, 748107970, 745916046, 607322378, 242269963, 451617315, 135967883,547822253, 313317750, 161488653, 301469277, 962913750, 674210017, 871684984, 846374473,601268294, 272544856, 214984956, 749089551, 450324802, 794618905, 329197003, 720425508,718926483, 494961133, 175588666, 199464056, 495851296, 10433899, 109859248, 258634838,147733353, 337233802, 299746629, 867784754, 831913393, 916124868, 415567211, 362520882,687700843, 108480217, 487643969, 798885287, 164330043, 141392377, 326198123, 395941595,161694806, 818547955, 461145285, 306055730, 597316323, 933967768, 13002237, 119645725,513592965, 196084977, 337595660, 887375487,];if n < cache.len() {cache[n]} else if n == 1 {1} else {(modpow(n, n) + MOD - (modfac(n) * super_binomial(n, n - 1, 0)) % MOD) % MOD}}fn next_configuration(conf: &mut [usize]) -> bool {let n = conf.len();for i in 0..n {if conf[i] != n - 1 {conf[i] += 1;return false;} else {conf[i] = 0;}}true}fn brute(n: usize) -> Vec<usize> {let mut res = vec![0; n];let mut conf = vec![0; n];// fn find_component(i: usize, conf: &[usize]) -> usize {// if conf[i] == i {// i// } else {// find_component(conf[i], conf)// }// }let mut last = 0;loop {if conf[n - 2] == last {println!("{}, {}", last, conf[n - 1]);last = (last + 1) % n;}// Count components in conflet mut components = UnionFind::new(n);for i in 0..n {components.union(i, conf[i]);}let mut component_list = Vec::new();for i in 0..n {component_list.push(components.find(i));}component_list.sort();component_list.dedup();res[n - component_list.len()] += 1;if next_configuration(&mut conf) {break;}}res}// n planets, of which k are not used, subset has at most max_s elements, there are already parts subsetsfn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {// assert!(max_s >= 1);// if k == 0 {// // No planets left.// res[parts - 1] += mul;// return;// }// // Try all possible sizes for the next subset// for s in 1..=max_s {// if k < s {// break;// }// subsolve(// n,// k - s,// s,// mul * binomial(s, k) * component_count(s),// parts + 1,// res,// );// }// todo!()}fn subsolve2(k: usize, max_s: usize, components: usize, tot: usize, res: &mut [usize]) {// println!(// "subsolve2(k={}, max_s={}, s_count={}, components={}, tot={})",// k, max_s, s_count, components, tot// );if k == 0 {res[components - 1] = (res[components - 1] + tot) % MOD;return;}// Try all possible sizes for the next subsetfor s in 1..=max_s {// Try to repeat s many timeslet mut extra = 1;for i in 1.. {if k < i * s {break;}// let mut extra = 1;extra = (extra * ((component_count(s) * modbin(s, k - s * (i - 1))) % MOD)) % MOD;extra = (extra * modpow(i, MOD - 2)) % MOD;subsolve2(k - i * s, s - 1, components + i, (tot * extra) % MOD, res);}}}fn solve(n: usize) -> Vec<usize> {let mut res = vec![0; n];let mut calls = BTreeMap::new();calls.insert(Reverse((n, n, 0)), 1);while let Some(call) = calls.iter().next() {let (Reverse((k, max_s, components)), tot) = call;let (k, max_s, components, tot) = (*k, *max_s, *components, *tot);// Remove the call from the stackcalls.remove(&Reverse((k, max_s, components)));if k == 0 {res[components - 1] = (res[components - 1] + tot) % MOD;continue;}for s in 1..=max_s {// Try to repeat s many timeslet mut extra = 1;for i in 1.. {if k < i * s {break;}// let mut extra = 1;extra = (extra * ((component_count(s) * modbin(s, k - s * (i - 1))) % MOD)) % MOD;extra = (extra * modpow(i, MOD - 2)) % MOD;// subsolve2(k - i * s, s - 1, components + i, (tot * extra) % MOD, res);let e = calls.entry(Reverse((k - i * s, s - 1, components + i))).or_insert(0);*e = (*e + tot * extra) % MOD;}}}// let mut res = vec![0; n];// // subsolve(n, n, n, 1, 0, &mut res);// subsolve2(n, n, 0, 1, &mut res);res.reverse();res// brute(n)// presolved(n)}fn main() {// unsafe {// cc_int_v.push(0);// };// for i in 1..=1000 {// unsafe {// cc_int_v.push(component_count(i));// };// println!("{}", i);// }// println!("{:?}", unsafe { &cc_int_v });// println!("{:#?}", unsafe { &stats });// println!("{:?}", solve(4));// return;let stdin = std::io::stdin();let stdin = stdin.lock();let mut lines = stdin.lines();let n: usize = lines.next().unwrap().unwrap().parse().unwrap();for v in solve(n).into_iter().rev() {println!("{}", v);}}// These are correct!fn presolved(n: usize) -> Vec<usize> {match n {1 => vec![1],2 => vec![1, 3],3 => vec![1, 9, 17],4 => vec![1, 18, 95, 142],5 => vec![1, 30, 305, 1220, 1569],6 => vec![1, 45, 745, 5595, 18694, 21576],7 => vec![1, 63, 1540, 18515, 113974, 334369, 355081],8 => vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296],9 => vec![1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153,].into_iter().map(|v| v % MOD).collect(),10 => vec![1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936, 3660215680,].into_iter().map(|v| v % MOD).collect(),_ => unimplemented!(),}}#[cfg(test)]mod tests {use super::*;#[test]fn test_component_count() {assert_eq!(component_count(1), 1);assert_eq!(component_count(2), 3);assert_eq!(component_count(3), 17);assert_eq!(component_count(4), 142);assert_eq!(component_count(5), 1569);assert_eq!(component_count(6), 21576);}#[test]fn test_samples() {assert_eq!(solve(1), vec![1]);assert_eq!(solve(2), vec![1, 3]);assert_eq!(solve(3), vec![1, 9, 17]);assert_eq!(solve(4), vec![1, 18, 95, 142]);assert_eq!(solve(5), vec![1, 30, 305, 1220, 1569]);assert_eq!(solve(6), vec![1, 45, 745, 5595, 18694, 21576]);assert_eq!(solve(7), vec![1, 63, 1540, 18515, 113974, 334369, 355081]);assert_eq!(solve(8),vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296]);assert_eq!(solve(9),vec![1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153].into_iter().map(|v| v % MOD).collect::<Vec<_>>());assert_eq!(solve(10),vec![1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936,3660215680].into_iter().map(|v| v % MOD).collect::<Vec<_>>());assert_eq!(solve(40),vec![966304277, 901371771, 759195442, 790481422, 122682607, 392000511, 435273028,966862670, 519723765, 30990597, 409125383, 2747902, 991199820, 296158387,176180602, 705066532, 401482496, 729626017, 207125017, 370405201, 417625468,45251194, 43175771, 793569343, 636114057, 198624360, 60099897, 166113870,925098106, 822029583, 434471173, 494653166, 760704585, 478566338, 96374759,235711347, 903105353, 2635490, 2340, 1].into_iter().rev().collect::<Vec<_>>());}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 |
correct output |
---|
3 1 |
user output |
---|
3 1 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
17 9 1 |
user output |
---|
17 9 1 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
142 95 18 1 |
user output |
---|
142 95 18 1 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 |
correct output |
---|
1569 1220 305 30 1 |
user output |
---|
1569 1220 305 30 1 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 |
correct output |
---|
21576 18694 5595 745 45 ... |
user output |
---|
21576 18694 5595 745 45 ... |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
7 |
correct output |
---|
355081 334369 113974 18515 1540 ... |
user output |
---|
355081 334369 113974 18515 1540 ... |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 |
correct output |
---|
6805296 6852460 2581964 484729 49840 ... |
user output |
---|
6805296 6852460 2581964 484729 49840 ... |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
9 |
correct output |
---|
148869153 158479488 64727522 13591116 1632099 ... |
user output |
---|
148869153 158479488 64727522 13591116 1632099 ... |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
660215659 85349908 783995053 409987640 55545735 ... |
user output |
---|
660215659 85349908 783995053 409987640 55545735 ... |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 |
correct output |
---|
8033007 474885151 998010619 720259168 345757330 ... |
user output |
---|
8033007 474885151 998010619 720259168 345757330 ... Truncated |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
50 |
correct output |
---|
637699856 613177596 194234103 50828885 988168359 ... |
user output |
---|
637699856 613177596 194234103 50828885 988168359 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 |
correct output |
---|
894456323 406549429 962038245 430640330 61348310 ... |
user output |
---|
894456323 406549429 962038245 430640330 61348310 ... Truncated |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
666 |
correct output |
---|
189730587 968711879 553374698 53051125 139917248 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
3333 |
correct output |
---|
79235821 455292218 627100211 591681254 695866885 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4991 |
correct output |
---|
482116496 245260697 151422537 180441123 318466624 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4992 |
correct output |
---|
141010647 787351178 684701591 872974815 631476284 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4993 |
correct output |
---|
504034249 588971460 281533415 928250892 416697844 ... |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4994 |
correct output |
---|
266134603 90079109 544661648 812099750 17249410 ... |
user output |
---|
(empty) |
Test 20
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4995 |
correct output |
---|
833898560 663839791 109127071 321675160 86285359 ... |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4996 |
correct output |
---|
721158645 167929822 115103278 491345159 114397872 ... |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4997 |
correct output |
---|
691405606 436947443 82656395 514529009 783319673 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4998 |
correct output |
---|
829675470 688714502 189351950 956110193 20883331 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4999 |
correct output |
---|
343936737 47032567 190931571 827280581 160866637 ... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
5000 |
correct output |
---|
364064601 633559852 352848841 666954216 428009512 ... |
user output |
---|
(empty) |