結果

問題 No.2465 Dilated Water Simulation
コンテスト
ユーザー 👑 ygussany
提出日時 2023-09-08 23:30:59
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,089 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 32,128 KB
実行使用メモリ 14,008 KB
最終ジャッジ日時 2024-06-26 16:56:55
合計ジャッジ時間 4,534 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

void naive(int L, int V[], long long N, int ans[])
{
	int i, j, k, x;
	for (i = 2, ans[1] = V[1]; i <= L; i++) ans[i] = 0;
	for (i = 0, j = 1, k = 2; i < N; i++, j++, k++) {
		if (j > L) j = 1;
		if (k > L) k = 1;
		x = (ans[j] <= V[k] - ans[k])? ans[j]: V[k] - ans[k];
		ans[j] -= x;
		ans[k] += x;
		for (x = 1; x <= L; x++) printf("%d ", ans[x]);
		printf("\n");
	}
}

void naive2(int L, int V[], long long N, int ans[])
{
	int i, j, k, x, prev[200001];
	for (i = 2, ans[1] = V[1]; i <= L; i++) ans[i] = 0;
	for (i = 1; i <= L; i++) prev[i] = 0;
	for (i = 0, j = 1, k = 2; i < N; i++, j++, k++) {
		if (j > L) j = 1;
		if (k > L) k = 1;
		if (j == 1) {
			for (x = 1; x <= L; x++) if (ans[x] != prev[x]) break;
			if (x <= L) {
				for (x = 1; x <= L; x++) prev[x] = ans[x];
			} else break;
		}
		
		x = (ans[j] <= V[k] - ans[k])? ans[j]: V[k] - ans[k];
		ans[j] -= x;
		ans[k] += x;
	}
	if (i < N) {
		N = (N - i) % L;
		for (i = 0, j = 1, k = 2; i < N; i++, j++, k++) {
			if (j > L) j = 1;
			if (k > L) k = 1;
			x = (ans[j] <= V[k] - ans[k])? ans[j]: V[k] - ans[k];
			ans[j] -= x;
			ans[k] += x;
		}
	}
}

void naive3(int L, int V[], long long N, int ans[])
{
	int i, j, k, x, min = 1 << 30;
	for (i = 2; i <= L; i++) {
		if (V[i] > V[1]) V[i] = V[1];
		if (min > V[i]) min = V[i];
	}
	for (i = 2; V[i] != min; i++);
	for (; i <= L; i++) V[i] = min;
	for (i = L; i >= 2 && V[i] == min; i--) ans[i] = 0;
	for (ans[1] = V[1]; i >= 2; i--) {
		x = (ans[1] - min <= V[i] - min)? ans[1] - min: V[i] - min;
		ans[i] = x;
		ans[1] -= x;
	}
	N = N % L;
	for (i = 0, j = 1, k = 2; i < N; i++, j++, k++) {
		if (j > L) j = 1;
		if (k > L) k = 1;
		x = (ans[j] <= V[k] - ans[k])? ans[j]: V[k] - ans[k];
		ans[j] -= x;
		ans[k] += x;
	}
}

int main()
{
	int i, L, V[200001];
	long long N;
	scanf("%d", &L);
	for (i = 1; i <= L; i++) scanf("%d", &(V[i]));
	scanf("%lld", &N);
	
	int ans[200001];
	if (N >= (long long)L * L * L) naive3(L, V, N, ans);
	else naive2(L, V, N, ans);
	for (i = 1; i <= L; i++) printf("%d ", ans[i]);
	printf("\n");
	fflush(stdout);
	return 0;
}
0