結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー pengin_2000
提出日時 2026-02-06 21:50:49
言語 C
(gcc 15.2.0)
結果
WA  
実行時間 -
コード長 874 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,503 ms
コンパイル使用メモリ 39,140 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-06 21:51:10
合計ジャッジ時間 10,367 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
int abs(int n)
{
	if (n < 0)
		n *= -1;
	return n;
}
int p[200005];
int ans[200005];
int v[200005];
int used[200005];
int main()
{
	int n;
	scanf("%d", &n);
	int i, j, k;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &p[i]);
		p[i]--;
	}
	for (i = 0; i < n; i++)
		ans[i] = 0;
	for (i = 0; i < n; i++)
		v[i] = -1;
	for (i = 0; i < n; i++)
		used[i] = 0;
	int d;
	for (i = 0; i < n; i++)
	{
		if (used[i] > 0)
			continue;
		used[i]++;
		for (j = i;;)
		{
			d = abs(p[j] - j);
			for (k = 1; k * k <= d; k++)
			{
				if (d % k > 0)
					continue;
				if (v[k] < i)
					v[k] = i;
				else
					ans[k]++;
				if (k * k < d)
				{
					k = d / k;
					if (v[k] < i)
						v[k] = i;
					else
						ans[k]++;
					k = d / k;
				}
			}
			j = p[j];
			if (j == i)
				break;
			used[j] = 1;
		}
	}
	for (i = 1; i < n; i++)
		printf("%d\n", ans[i]);
	return 0;
}
0