#635307 (C++17) No.1584 Stones around Circle Pond

提出ソース

結果

問題	No.1584 Stones around Circle Pond
ユーザー	nok0
提出日時	2021-03-28 13:44:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	2,849 bytes
コンパイル時間	2,330 ms
コンパイル使用メモリ	213,916 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-29 04:34:25
合計ジャッジ時間	3,960 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	2 ms 5,376 KB
testcase_17	WA	-
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	8 ms 5,376 KB
testcase_21	AC	4 ms 5,376 KB
testcase_22	AC	7 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	3 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	3 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	AC	2 ms 5,376 KB
testcase_47	WA	-
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	WA	-
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	AC	5 ms 5,376 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

static const double EPS = 1e-10;

template <class T>
struct Matrix {
	vector<vector<T> > val;
	Matrix(int n, int m, T x = 0) : val(n, vector<T>(m, x)) {}
	void init(int n, int m, T x = 0) { val.assign(n, vector<T>(m, x)); }
	size_t size() const { return val.size(); }
	inline vector<T>& operator[](int i) { return val[i]; }
};

template <class T>
int GaussJordan(Matrix<T>& A, bool is_extended = false) {
	int m = A.size(), n = A[0].size();
	int rank = 0;
	for(int col = 0; col < n; ++col) {
		// 拡大係数行列の場合は最後の列は掃き出ししない
		if(is_extended && col == n - 1) break;

		// ピボットを探す
		int pivot = -1;
		T ma = EPS;
		for(int row = rank; row < m; ++row) {
			if(abs(A[row][col]) > ma) {
				ma = abs(A[row][col]);
				pivot = row;
			}
		}
		// ピボットがなかったら次の列へ
		if(pivot == -1) continue;

		// まずは行を swap
		swap(A[pivot], A[rank]);

		// ピボットの値を 1 にする
		auto fac = A[rank][col];
		for(int col2 = 0; col2 < n; ++col2) A[rank][col2] /= fac;

		// ピボットのある列の値がすべて 0 になるように掃き出す
		for(int row = 0; row < m; ++row) {
			if(row != rank && abs(A[row][col]) > EPS) {
				auto fac = A[row][col];
				for(int col2 = 0; col2 < n; ++col2) {
					A[row][col2] -= A[rank][col2] * fac;
				}
			}
		}
		++rank;
	}
	return rank;
}

template <class T>
vector<T> linear_equation(Matrix<T> A, vector<T> b) {
	// extended
	int m = A.size(), n = A[0].size();
	Matrix<T> M(m, n + 1);
	for(int i = 0; i < m; ++i) {
		for(int j = 0; j < n; ++j) M[i][j] = A[i][j];
		M[i][n] = b[i];
	}
	int rank = GaussJordan(M, true);

	// check if it has no solution
	vector<T> res;
	for(int row = rank; row < m; ++row)
		if(abs(M[row][n]) > EPS) return res;

	// answer
	res.assign(n, 0);
	for(int i = 0; i < rank; ++i) res[i] = M[i][n];
	return res;
}

using ll = long long;

#define rep(i, x) for(int i = 0; i < (x); i++)

int main() {
	int n, l;
	cin >> n >> l;
	vector d(n, 0ll), b(2 * n, 0ll);
	for(auto& v : d) cin >> v;
	for(auto& v : b) cin >> v;
	auto dist = [&](ll x, ll y) {
		if(x > y) swap(x, y);
		return min(y - x, x + 2 * l - y);
	};

	Matrix<long double> mat(n * 2 + 1, n * 2, 1);
	auto pl = [&](int i) {
		return (i < n ? d[i] : d[i - n] + l);
	};
	rep(i, 2 * n) {
		rep(j, 2 * n) {
			mat[i][j] = dist(pl(i), pl(j));
		}
	}
	ll z = b[0] + b[n];
	if(z % l) {
		puts("No");
		return 0;
	}
	z /= l;
	rep(i, n) {
		if(b[i] + b[n + i] != z * l) {
			puts("No");
			return 0;
		}
	}
	vector<long double> c(2 * n);
	rep(i, 2 * n) c[i] = b[i];

	c.push_back(z);

	auto res = linear_equation(mat, c);

	if(res.empty()) {
		puts("No");
		return 0;
	}

	for(auto& v : res) {
		ll x = round(v);
		if(x < 0 or abs(v - x) > EPS) {
			puts("No");
			return 0;
		}
	}

	puts("Yes");
}

yukicoder

結果

テストケース

ソースコード