#324264 (C++17) No.856 増える演算

提出ソース

結果

問題	No.856 増える演算
ユーザー	CuriousFairy315
提出日時	2019-03-17 18:24:56
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	2,950 bytes
コンパイル時間	860 ms
コンパイル使用メモリ	81,352 KB
実行使用メモリ	4,512 KB
最終ジャッジ日時	2023-07-30 20:50:42
合計ジャッジ時間	6,371 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	1 ms 4,380 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	9 ms 4,376 KB
testcase_24	AC	12 ms 4,376 KB
testcase_25	AC	3 ms 4,376 KB
testcase_26	AC	2 ms 4,380 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	9 ms 4,376 KB
testcase_29	AC	8 ms 4,376 KB
testcase_30	AC	7 ms 4,380 KB
testcase_31	AC	4 ms 4,376 KB
testcase_32	AC	10 ms 4,376 KB
testcase_33	AC	21 ms 4,376 KB
testcase_34	AC	43 ms 4,380 KB
testcase_35	AC	27 ms 4,380 KB
testcase_36	AC	40 ms 4,376 KB
testcase_37	AC	35 ms 4,380 KB
testcase_38	AC	5 ms 4,376 KB
testcase_39	AC	8 ms 4,380 KB
testcase_40	AC	16 ms 4,380 KB
testcase_41	AC	17 ms 4,380 KB
testcase_42	AC	47 ms 4,376 KB
testcase_43	AC	17 ms 4,376 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	8 ms 4,376 KB
testcase_46	AC	18 ms 4,380 KB
testcase_47	AC	15 ms 4,380 KB
testcase_48	AC	29 ms 4,380 KB
testcase_49	AC	20 ms 4,380 KB
testcase_50	AC	31 ms 4,376 KB
testcase_51	AC	41 ms 4,376 KB
testcase_52	AC	45 ms 4,376 KB
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	-

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

ソースコード

raw source code

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdint>
using namespace std; // 575

const int MAX = 100000;
const int MAX2 = 1000;
const int MOD = 1000000007; // 今回使う余り

int64_t pow(int64_t n, int m, int mod) {
	if (m == 0) return 1;
	if (m == 1) return n;
	if (m == 2) return n * n % mod;
	return pow(pow(n, m / 2, mod), 2, mod) * pow(n, m & 1, mod) % mod;
}
int main() {
	int N;
	static int A[MAX];
	cin >> N;
	if (N < 2 || N > MAX) {
		cout << "No Judge";
		return 0;
	}
	for (int i = 0;i < N;++ i) {
		cin >> A[i];
		if (A[i] < 1 || A[i] > MAX2) {
			cout << "No Judge";
			return 0;
		}
	}
	
	int count[MAX2 + 1], add[2 * MAX2 + 1], sum = 0;
	static double mini = log(A[0] + A[1]) + A[1] * log(A[0]);
	static pair<int, int> minimum = make_pair(A[0], A[1]);
	int64_t ans = 1;
	for (int i = 0;i <= MAX2;++ i) count[i] = 0;
	for (int i = 0;i <= 2 * MAX2;++ i) add[i] = 0;
	for (int i = 0;i < N;++ i) {
		++ count[A[i]]; // バケット
		sum += A[i];
	}
	for (int i = 0, j = 0;i < N;++ i) {
		-- count[A[i]];
		sum -= A[i];
		while (!count[j]) ++ j;
		if (mini > log(A[i] + j) + j * log(A[i])) {
			mini = log(A[i] + j) + j * log(A[i]);
			minimum = make_pair(A[i], j);
		}
		for (int k = j;k <= MAX2;++ k) add[A[i] + k] += count[k];
		ans = ans * pow(A[i], sum, MOD) % MOD;
	}
	for (int i = 0;i < 2 * MAX2 + 1;++ i) if (add[i]) ans = ans * pow(i, add[i], MOD) % MOD;
	ans = ans * pow(minimum.first + minimum.second, MOD - 2, MOD) % MOD * pow(pow(minimum.first, minimum.second, MOD), MOD - 2, MOD) % MOD;
	cout << ans << endl;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

まず、とっとと最小の要素を特定してしまうことを考える
指数が厄介なので、先にiの方を固定する
この時、jはiより大きい値の中でA_j最小であることは自明であるから、セグメント木などを使うとO(logN)で候補を取り出せる
これを各iについてやると全部でN個の候補ができて、その中で最小のものは実際に比較すれば良い
これらの操作により、O(N(logN+logA))で最小の値が求まる
次に、全ての積を求める
また、iを固定して考えていく
各iについて、和に関してはA_jの値の範囲が狭いことからバケットソートをすればO(A)で求めることができ、
指数に関しては積上では和の計算に等しいからsum(A_j)をすればよくて、これは前もって計算しておけば良い
これによって、O(A(N+logA))で全ての積が求まった
後は割る操作に関してはフェルマーの定理でも使えばいいし、使わなくても答えは求まる
最終的に、計算量はO(NA+NlogN+(N+A)logA)となる
*/

yukicoder

結果

テストケース

ソースコード