#362934 (C++17) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	MarcusAureliusAntoninus
提出日時	2019-07-26 23:12:16
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	1,908 bytes
コンパイル時間	2,403 ms
コンパイル使用メモリ	209,388 KB
実行使用メモリ	24,320 KB
最終ジャッジ日時	2024-07-02 09:20:09
合計ジャッジ時間	24,977 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	4 ms 6,944 KB
testcase_23	AC	5 ms 6,940 KB
testcase_24	AC	8 ms 6,940 KB
testcase_25	AC	5 ms 6,940 KB
testcase_26	AC	9 ms 6,940 KB
testcase_27	AC	7 ms 6,940 KB
testcase_28	AC	4 ms 6,940 KB
testcase_29	AC	3 ms 6,940 KB
testcase_30	AC	4 ms 6,940 KB
testcase_31	AC	9 ms 6,940 KB
testcase_32	AC	117 ms 7,936 KB
testcase_33	AC	137 ms 6,940 KB
testcase_34	AC	270 ms 9,472 KB
testcase_35	AC	181 ms 8,064 KB
testcase_36	AC	67 ms 6,940 KB
testcase_37	AC	114 ms 7,552 KB
testcase_38	AC	86 ms 7,040 KB
testcase_39	AC	433 ms 9,728 KB
testcase_40	AC	150 ms 6,940 KB
testcase_41	AC	180 ms 7,168 KB
testcase_42	AC	230 ms 9,472 KB
testcase_43	AC	292 ms 7,424 KB
testcase_44	AC	305 ms 8,960 KB
testcase_45	AC	226 ms 6,944 KB
testcase_46	AC	412 ms 8,832 KB
testcase_47	AC	135 ms 6,940 KB
testcase_48	AC	208 ms 9,216 KB
testcase_49	AC	190 ms 9,344 KB
testcase_50	AC	101 ms 7,552 KB
testcase_51	AC	410 ms 8,960 KB
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	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	AC	457 ms 24,192 KB
testcase_84	AC	1,259 ms 24,192 KB
testcase_85	AC	496 ms 23,808 KB
testcase_86	AC	51 ms 23,680 KB
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	AC	1,633 ms 24,192 KB
testcase_93	AC	1,622 ms 24,192 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

using vi = std::vector<int64_t>;
using vvi = std::vector<vi>;

int N;
vvi smallPrime, largePrime;
vi primeTable, zeroCount;

void makePrimeTable()
{
	std::vector<bool> isPrime(2'001, true);
	for (int i{2}; i <= 2'000; i++)
	{
		if (!isPrime[i]) continue;
		primeTable.push_back(i);
		if (i <= 100) smallPrime.push_back(vi(N + 1));
		else largePrime.push_back({});
		for (int j{2 * i}; j <= 2'000; j += i)
			isPrime[j] = false;
	}
}

bool dividable()
{
	int64_t P;
	int L, R;
	scanf("%lld%d%d", &P, &L, &R);
	for (int p_i{}; p_i < (int)smallPrime.size() && P > 1; p_i++)
	{
		int count{};
		while (P % primeTable[p_i] == 0)
		{
			P /= primeTable[p_i];
			count++;
		}
		if (smallPrime[p_i][R] - smallPrime[p_i][L - 1] < count) return false;
	}
	if (P == 1) return true;
	for (int p_i{}; p_i < (int)largePrime.size() && P > 1; p_i++)
	{
		int count{};
		while (P % primeTable[smallPrime.size() + p_i] == 0)
		{
			P /= primeTable[smallPrime.size() + p_i];
			count++;
		}
		if (std::upper_bound(largePrime[p_i].begin(), largePrime[p_i].end(), R) - std::lower_bound(largePrime[p_i].begin(), largePrime[p_i].end(), L) < count)
			return false;
	}
	return P == 1;
}

int main()
{
	scanf("%d", &N);
	makePrimeTable();
	zeroCount.resize(N + 1);
	for (int n_i{1}; n_i <= N; n_i++)
	{
		int A;
		scanf("%d", &A);
		zeroCount[n_i] += zeroCount[n_i - 1];
		if (A == 0)
		{
			zeroCount[n_i]++;
			continue;
		}
		for (int p_i{}; p_i < (int)smallPrime.size(); p_i++)
		{
			while (A % primeTable[p_i] == 0)
			{
				A /= primeTable[p_i];
				smallPrime[p_i][n_i]++;
			}
			smallPrime[p_i][n_i] += smallPrime[p_i][n_i - 1];
		}
		for (int p_i{}; p_i < (int)largePrime.size(); p_i++)
			if (A % primeTable[smallPrime.size() + p_i] == 0)
				largePrime[p_i].push_back(n_i);
	}
	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
		if (dividable()) puts("Yes");
		else puts("NO");

	return 0;
}

yukicoder

結果

テストケース

ソースコード