結果

問題 No.1584 Stones around Circle Pond
コンテスト
ユーザー nok0
提出日時 2021-05-17 10:43:10
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,387 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,100 ms
コンパイル使用メモリ 198,716 KB
最終ジャッジ日時 2025-01-21 13:22:02
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

void fin() {
	puts("No");
	exit(0);
}

int main() {
	int n, l;
	cin >> n >> l;
	vector d(n * 2, 0), b(2 * n, 0);
	for(int i = 0; i < n; i++) cin >> d[i], d[i + n] = d[i] + l;
	for(auto &v : b) cin >> v;

	vector cum(n, 0ll);
	for(int i = 0; i < n; i++) {
		if((b[i + 1] - b[i]) % (d[i + 1] - d[i]) or b[i + 1] - b[i] != b[n + i] - b[(n + i + 1) % (2 * n)]) fin();
		cum[i] = (b[i + 1] - b[i]) / (d[i + 1] - d[i]);
	}

	vector ans(n, 0ll);
	for(int i = 0; i < n; i++) {
		if(i) {
			if((cum[i] - cum[i - 1]) % 2) fin();
			ans[i] = (cum[i] - cum[i - 1]) / 2;
		} else {
			if((cum[0] + cum[n - 1]) % 2) fin();
			ans[i] = (cum[0] + cum[n - 1]) / 2;
		}
	}

	for(int i = 0; i < n; i++) {
		if(ans[i] > 0) {
			for(int j = 0; j < i; j++) {
				b[j] -= ans[i] * (d[i] - d[j]);
			}
			for(int j = i; j < n + i; j++) {
				b[j] -= ans[i] * (d[j] - d[i]);
			}
			for(int j = n + i; j < 2 * n; j++) {
				b[j] -= ans[i] * (2 * l - d[j] + d[i]);
			}
		} else {
			for(int j = 0; j < i; j++) {
				b[j] += ans[i] * (2 * l + d[j] - d[i + n]);
			}
			for(int j = i; j < i + n; j++) {
				b[j] += ans[i] * (d[i + n] - d[j]);
			}
			for(int j = i + n; j < 2 * n; j++) {
				b[j] += ans[i] * (d[j] - d[i + n]);
			}
		}
	}
	for(int i = 0; i < 2 * n; i++) {
		if(b[i] != b[(i + 1) % (2 * n)]) fin();
	}
	if(b[0] < 0 or b[0] % l) fin();
	puts("Yes");
}
0