結果
問題 | No.295 hel__world |
ユーザー | te-sh |
提出日時 | 2018-02-01 15:09:42 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,715 bytes |
コンパイル時間 | 9,308 ms |
コンパイル使用メモリ | 327,472 KB |
実行使用メモリ | 10,784 KB |
最終ジャッジ日時 | 2024-06-12 23:44:46 |
合計ジャッジ時間 | 18,291 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 TLE * 1 WA * 1 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;import std.container; // SList, DList, BinaryHeapimport std.bigint; // BigIntimport std.regex; // Regexvoid readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}const inf = BigInt(1L<<62);void main(){auto s = readArray!long(26);string t; readV(t);auto d = BigInt(1);foreach (i, si; s) {d *= calc(BigInt(si), t, cast(char)('a'+i));if (d >= inf) {writeln("hel");return;}}writeln(d);}auto calc(BigInt s, string t, char c){auto y = t.matchAll(regex(c.to!string ~ '+')).map!((m) => m[0].length.to!int).array;auto ny = y.length.to!int;if (y.empty) return BigInt(1);if (s < y.sum) return BigInt(0);if (s > 10^^7) {if (ny == 1) {if (y[0] == 1) return s;if (y[0] == 2) return s*(s-1)/2;} else if (ny == 2) {if (y[0] == 1 && y[1] == 1) return s/2*(s-s/2);}return inf;}auto r = new Rat[](ny);foreach (i, yi; y)r[i] = Rat(BigInt(yi+1), BigInt(1), yi+1, yi);auto h = heapify(r), d = BigInt(1);foreach (i; 0..(s-y.sum).to!int) {auto ri = h.front;d = d * ri.num / ri.den;if (d >= inf) return inf;h.replaceFront(Rat(BigInt(ri.n+1), BigInt(ri.n+1-ri.r), ri.n+1, ri.r));}return d;}struct Rat{BigInt num, den;int n, r;auto opCmp(Rat b){auto c = num*b.den - b.num*den;return c == 0 ? 0 : c < 0 ? -1 : 1;}}