結果
| 問題 | No.295 hel__world |
| ユーザー |
 uwi
|
| 提出日時 | 2015-10-23 05:32:35 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,148 ms / 5,000 ms |
| コード長 | 6,584 bytes |
| コンパイル時間 | 4,663 ms |
| コンパイル使用メモリ | 89,724 KB |
| 実行使用メモリ | 86,004 KB |
| 最終ジャッジ日時 | 2024-07-22 23:03:39 |
| 合計ジャッジ時間 | 17,596 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 53 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;import java.util.InputMismatchException;import java.util.PriorityQueue;public class Q400T {InputStream is;PrintWriter out;String INPUT = "";void solve(){long[] s = new long[26];for(int i = 0;i < 26;i++){s[i] = nl();if(s[i] < 0 || s[i] > 1_000_000_000_000_000_000L)throw new RuntimeException("s[i] out of range");}char[] t = ns().toCharArray();if(t.length < 1 || t.length > 1_000_000)throw new RuntimeException("t out of range");for(char c : t){if(!('a' <= c && c <= 'z'))throw new RuntimeException("t invalid char");}int n = t.length;// 0?int[] freq = new int[26];for(char c : t){freq[c-'a']++;}for(int i = 0;i < 26;i++){if(s[i] < freq[i]){out.println(0);return;}}long ret = 1;double retd = 1;int[] lens = new int[n+1];for(char x = 'a';x <= 'z';x++){int xi = x-'a';int len = 0;int p = 0;for(int i = 0;i < n;i++){if(t[i] == x){len++;}else{if(len > 0)lens[p++] = len;len = 0;}}if(len > 0)lens[p++] = len;if(p == 0)continue;if(p == 1 && lens[0] == 1){// 1ret *= s[xi];retd *= s[xi];if(retd > 3L<<61 || ret >= 1L<<62){out.println("hel"); return;}continue;}if(p == 1 && lens[0] == 2){// 2if(s[xi] >= 5_000_000_000L){out.println("hel"); return;}long w0 = s[xi];long w1 = s[xi]-1;if(w0 % 2 == 0){w0 /= 2;}else{w1 /= 2;}ret *= w0 * w1;retd *= w0 * w1;if(retd > 3L<<61 || ret >= 1L<<62){out.println("hel"); return;}continue;}if(p == 2 && lens[0] == 1 && lens[1] == 1){// 1 1long w0 = s[xi]/2;long w1 = (s[xi]+1)/2;if(w0 >= 3_000_000_000L){out.println("hel"); return;}ret *= w0 * w1;retd *= w0 * w1;if(retd > 3L<<61 || ret >= 1L<<62){out.println("hel"); return;}continue;}for(int i = 0;i < p;i++){s[xi] -= lens[i];}if(s[xi] < 0){// impossibleout.println(0);return;}// {v, d}PriorityQueue<int[]> pq = new PriorityQueue<>(1000, new Comparator<int[]>(){public int compare(int[] a, int[] b){// (v1+d1)/d1 >= (v2+d2)/d2return -Long.compare((long)(a[0]+a[1]+1)*(b[1]+1), (long)(b[0]+b[1]+1)*(a[1]+1));}});for(int i = 0;i < p;i++){pq.add(new int[]{lens[i], 0});}double lretd = retd;while(!pq.isEmpty() && s[xi] > 0){int[] cur = pq.poll();cur[1]++;lretd = lretd * (cur[0] + cur[1]) / cur[1];if(lretd >= 3L<<61){out.println("hel"); return;}pq.add(cur);s[xi]--;}while(!pq.isEmpty()){int[] cur = pq.poll();long val = CI(cur[0]+cur[1], cur[1]);if(val == -1){out.println("hel"); return;}ret *= val;retd *= val;if(retd > 3L<<61 || ret >= 1L<<62){out.println("hel"); return;}}}out.println(ret);}// public static long CIX(long n, int r)// {// if(n < 0 || r < 0 || r > n)return 0;// long u = 1;// for(int i = 0;i < r;i++){// u = u * (n-i) / (i+1);// }// return u;// }public static long CI(long n, int r){if(n < 0 || r < 0 || r > n)return 0;long[] a = new long[r];int[] b = new int[r];for(int i = 0;i < r;i++){a[i] = n-i;b[i] = i+1;}for(int i = 0;i < r;i++){int p = b[i];if(p == 1)continue;for(int j = i, k = (int)(n%(i+1));j < r;j += i+1, k += i+1){a[k] /= p;b[j] /= p;}}long mul = 1;double muld = 1;for(int i = 0;i < r;i++){mul = mul * a[i];muld = muld * a[i];}if(muld >= 3L<<61)return -1;return mul;}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}public static void main(String[] args) throws Exception { new Q400T().run(); }private byte[] inbuf = new byte[1024];private int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private char[][] nm(int n, int m) {char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m) {int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int ni() { return (int)nl(); }private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}