結果

問題 No.1584 Stones around Circle Pond
コンテスト
ユーザー nok0
提出日時 2021-03-28 13:44:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,849 bytes
コンパイル時間 3,157 ms
コンパイル使用メモリ 205,344 KB
最終ジャッジ日時 2025-01-20 00:11:42
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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");
}
0