結果
問題 | No.2734 Addition and Multiplication in yukicoder (Hard) |
ユーザー | ks2m |
提出日時 | 2024-04-19 23:01:48 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,214 bytes |
コンパイル時間 | 3,299 ms |
コンパイル使用メモリ | 78,944 KB |
実行使用メモリ | 69,364 KB |
最終ジャッジ日時 | 2024-04-19 23:02:15 |
合計ジャッジ時間 | 14,245 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
42,740 KB |
testcase_01 | AC | 46 ms
37,104 KB |
testcase_02 | AC | 46 ms
37,212 KB |
testcase_03 | AC | 48 ms
36,844 KB |
testcase_04 | AC | 47 ms
36,916 KB |
testcase_05 | AC | 47 ms
37,048 KB |
testcase_06 | AC | 48 ms
37,120 KB |
testcase_07 | AC | 47 ms
36,692 KB |
testcase_08 | AC | 53 ms
37,188 KB |
testcase_09 | AC | 46 ms
37,220 KB |
testcase_10 | AC | 46 ms
37,356 KB |
testcase_11 | AC | 45 ms
36,960 KB |
testcase_12 | AC | 45 ms
37,460 KB |
testcase_13 | AC | 47 ms
37,172 KB |
testcase_14 | AC | 54 ms
37,156 KB |
testcase_15 | AC | 47 ms
37,120 KB |
testcase_16 | AC | 47 ms
37,320 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 100 ms
40,356 KB |
testcase_20 | AC | 119 ms
44,384 KB |
testcase_21 | TLE | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static List<List<String>> list; static int[] idx, size; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); list = new ArrayList<>(20); for (int i = 0; i < 20; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { list.get(sa[i].length()).add(sa[i]); } br.close(); size = new int[20]; for (int i = 0; i < 20; i++) { size[i] = list.get(i).size(); Collections.sort(list.get(i)); } int mod = 998244353; StringBuilder sb = new StringBuilder(); idx = new int[20]; for (int i = 0; i < n - 1; i++) { for (int j = 19; j > 0; j--) { if (idx[j] < size[j]) { min = list.get(j).get(idx[j]); mini = j; break; } } for (int j = mini - 1; j > 0; j--) { if (idx[j] < size[j]) { String s = list.get(j).get(idx[j]); if (s.compareTo(min.substring(0, j)) < 0) { min = s; mini = j; } } } for (int j = mini - 1; j > 0; j--) { if (idx[j] < size[j]) { StringBuilder sb2 = new StringBuilder(); sb2.append(list.get(j).get(idx[j])); idx[j]++; dfs(sb2, j); idx[j]--; } } sb.append(list.get(mini).get(idx[mini])); idx[mini]++; } for (int j = 1; j < 20; j++) { if (idx[j] < size[j]) { sb.append(list.get(j).get(idx[j])); break; } } long ans = 0; for (int i = 0; i < sb.length(); i++) { int d = sb.charAt(i) - '0'; ans *= 10; ans += d; ans %= mod; } System.out.println(ans); } static String min; static int mini; static void dfs(StringBuilder sb, int f) { if (sb.length() >= min.length()) { String s = sb.toString(); if (s.compareTo(min) < 0) { min = s; mini = f; } return; } for (int i = 19; i > 0; i--) { if (idx[i] < size[i]) { sb.append(list.get(i).get(idx[i])); idx[i]++; if (sb.toString().compareTo(min) < 0) { dfs(sb, f); } idx[i]--; sb.delete(sb.length() - i, sb.length()); } } } }