#835427 (C++14) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: _dehachi
• 提出日時: 2023-01-25 22:50:01
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 980 bytes
• コンパイル時間: 2,022 ms
• コンパイル使用メモリ: 181,320 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-27 00:21:04
• 合計ジャッジ時間: 2,852 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB

コンパイルメッセージ

main.cpp: In member function 'std::pair<_FIter, _FIter> CRT<T>::calc()':
main.cpp:27:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   27 |                         auto [p, q, d] = ext_gcd(m, mod[i]);
      |                              ^
main.cpp: In function 'void solve()':
main.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   44 |         auto [r, m] = crt.calc();
      |              ^

ソースコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <typename T>
struct CRT {
	vector<T> rem, mod;
	void add(T r, T m) {
		rem.emplace_back(r);
		mod.emplace_back(m);
	}
	pair<T,T> calc() {
		T r = 0, m = 1;
		for (int i=0; i<(int)rem.size(); i++) {
			auto ext_gcd = [](T a, T b) -> tuple<T,T,T> {
				T x = 1, y = 0, u = 0, v = 1;
				while (b) {
					T p = a/b, q = a%b, r = x-u*p;
					x = u, u = r;
					r = y-v*p;
					y = v, v = r;
					a = b, b = q;
				}
				return {x,y,a};
			};
			auto [p, q, d] = ext_gcd(m, mod[i]);
			if ((rem[i]-r)%d != 0) return {0, 0};
			T t = (rem[i]-r)/d*p%(mod[i]/d);
			r += m*t;
			m *= mod[i]/d;
		}
		return {r<0?r+m:r, m};
	}
};

void solve() {
	CRT<ll> crt;
	for (int i=0; i<3; i++) {
		ll x, y;
		cin >> x >> y;
		crt.add(x, y);
	}
	auto [r, m] = crt.calc();
	cout << (m?r:-1) << '\n';
}

signed main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	solve();
	return 0;
}