#363070 (Java21) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	ks2m
提出日時	2019-07-27 00:11:20
言語	Java21 (openjdk 21)
結果	MLE
実行時間	-
コード長	2,435 bytes
コンパイル時間	2,735 ms
コンパイル使用メモリ	79,588 KB
実行使用メモリ	747,288 KB
最終ジャッジ日時	2024-07-02 10:16:34
合計ジャッジ時間	84,508 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 44,248 KB
testcase_01	AC	50 ms 36,964 KB
testcase_02	AC	46 ms 37,056 KB
testcase_03	AC	47 ms 37,168 KB
testcase_04	AC	49 ms 36,756 KB
testcase_05	AC	50 ms 36,964 KB
testcase_06	AC	48 ms 37,168 KB
testcase_07	AC	47 ms 36,908 KB
testcase_08	AC	50 ms 36,892 KB
testcase_09	AC	47 ms 37,184 KB
testcase_10	AC	48 ms 36,736 KB
testcase_11	AC	49 ms 37,036 KB
testcase_12	AC	51 ms 36,884 KB
testcase_13	AC	52 ms 36,880 KB
testcase_14	AC	48 ms 37,168 KB
testcase_15	AC	48 ms 36,932 KB
testcase_16	AC	51 ms 36,808 KB
testcase_17	AC	49 ms 36,880 KB
testcase_18	AC	49 ms 37,180 KB
testcase_19	AC	51 ms 36,880 KB
testcase_20	AC	50 ms 36,956 KB
testcase_21	AC	52 ms 36,952 KB
testcase_22	AC	122 ms 40,452 KB
testcase_23	AC	125 ms 42,072 KB
testcase_24	AC	169 ms 47,008 KB
testcase_25	AC	120 ms 40,712 KB
testcase_26	AC	174 ms 47,540 KB
testcase_27	AC	159 ms 47,192 KB
testcase_28	AC	111 ms 40,284 KB
testcase_29	AC	100 ms 39,620 KB
testcase_30	AC	121 ms 41,316 KB
testcase_31	AC	156 ms 47,368 KB
testcase_32	MLE	-
testcase_33	AC	1,254 ms 199,216 KB
testcase_34	MLE	-
testcase_35	MLE	-
testcase_36	AC	336 ms 61,368 KB
testcase_37	MLE	-
testcase_38	AC	1,378 ms 281,404 KB
testcase_39	MLE	-
testcase_40	AC	952 ms 165,628 KB
testcase_41	AC	1,547 ms 281,372 KB
testcase_42	MLE	-
testcase_43	MLE	-
testcase_44	MLE	-
testcase_45	AC	827 ms 122,940 KB
testcase_46	MLE	-
testcase_47	AC	1,281 ms 221,212 KB
testcase_48	MLE	-
testcase_49	MLE	-
testcase_50	AC	1,402 ms 279,144 KB
testcase_51	MLE	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	MLE	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	MLE	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	MLE	-
testcase_74	MLE	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	MLE	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	MLE	-
testcase_83	--	-
testcase_84	--	-
testcase_85	--	-
testcase_86	--	-
testcase_87	--	-
testcase_88	--	-
testcase_89	--	-
testcase_90	--	-
testcase_91	--	-
testcase_92	--	-
testcase_93	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		sa = br.readLine().split(" ");
		int[] a = new int[n];
		TreeSet<Integer> zero = new TreeSet<>();
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sa[i]);
			if (a[i] == 0) {
				zero.add(i);
			}
		}
		sa = br.readLine().split(" ");
		int q = Integer.parseInt(sa[0]);

		List<Map<Integer, Integer>> list = new ArrayList<>(n);
		list.add(new HashMap<>());
		for (int i = 0; i < n; i++) {
			Map<Integer, Integer> soinsu = bunkai(a[i]);
			for (Integer o : list.get(i).keySet()) {
				if (soinsu.containsKey(o)) {
					soinsu.put(o, soinsu.get(o) + list.get(i).get(o));
				} else {
					soinsu.put(o, list.get(i).get(o));
				}
			}
			list.add(soinsu);
		}

		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			int p0 = Integer.parseInt(sa[0]);
			int p1 = Integer.parseInt(sa[1]);
			int p2 = Integer.parseInt(sa[2]);
			if (p0 == 1) {
				pw.println("Yes");
				continue;
			}
			if (zero.ceiling(p1 - 1) != null && zero.floor(p2 - 1) != null) {
				pw.println("NO");
				continue;
			}
			Map<Integer, Integer> soinsu = bunkai(p0);
			Map<Integer, Integer> l = list.get(p1 - 1);
			Map<Integer, Integer> r = list.get(p2);
			boolean flg = true;
			for (Integer o : soinsu.keySet()) {
				int x = soinsu.get(o);
				Integer y = l.get(o);
				if (y == null) y = 0;
				Integer z = r.get(o);
				if (z == null) z = 0;
				if (x > z - y) {
					flg = false;
					break;
				}
			}
			if (flg) {
				pw.println("Yes");
			} else {
				pw.println("NO");
			}
		}
		pw.flush();
	}

	static Map<Integer, Integer> bunkai(int n) {
		Map<Integer, Integer> soinsu = new HashMap<>();
		int end = (int) Math.sqrt(n);
		int d = 2;
		while (n > 1) {
			if (n % d == 0) {
				n /= d;
				if (soinsu.containsKey(d)) {
					soinsu.put(d, soinsu.get(d) + 1);
				} else {
					soinsu.put(d, 1);
				}
				end = (int) Math.sqrt(n);
			} else {
				if (d > end) {
					d = n - 1;
				}
				d++;
			}
		}
		return soinsu;
	}
}

yukicoder

結果

テストケース

ソースコード