結果

問題 No.3269 Leq-K Partition
コンテスト
ユーザー pengin_2000
提出日時 2025-09-12 22:37:36
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 3,618 ms / 6,000 ms
コード長 1,181 bytes
コンパイル時間 1,019 ms
コンパイル使用メモリ 26,540 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-12 23:43:39
合計ジャッジ時間 60,893 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:33:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |         scanf("%d", &n);
      |         ^~~~~~~~~~~~~~~
main.c:36:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |                 scanf("%d", &a[i]);
      |                 ^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
int a[100005];
int cnt[100005];
int n;
int cal(int w)
{
	int count = 0, i, j, res = 1;
	for (i = j = 0; i < n; i++)
	{
		if (cnt[a[i]] > 0)
			continue;
		if (count == w)
		{
			for (; j < i; j++)
				cnt[a[j]] = 0;
			cnt[a[i]]++;
			count = 1;
			res++;
		}
		else
		{
			count++;
			cnt[a[i]]++;
		}
	}
	for (; j < n; j++)
		cnt[a[j]] = 0;
	return res;
}
int ans[100005];
int main()
{
	scanf("%d", &n);
	int i, j, k;
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (i = 0; i <= n; i++)
		ans[i] = -1;
	for (i = 0; i < n; i++)
		cnt[i] = 0;
	for (i = 0; i < n; i++)
		a[i]--;
	int sq;
	for (sq = 1; sq * sq < n; sq++);
	int min, mid, max, left, right;
	for (k = 1; k <= sq; k++)
		ans[k] = cal(k);
	for (k = sq; k > 0; k--)
	{
		min = 0;
		max = n + 1;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (cal(mid) > k)
				min = mid;
			else
				max = mid;
		}
		left = max;
		min = 0;
		max = n + 1;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (cal(mid) < k)
				max = mid;
			else
				min = mid;
		}
		right = max;
		for (i = left; i < right; i++)
			ans[i] = k;
	}
	for (i = 1; i <= n; i++)
		printf("%d\n", ans[i]);
	return 0;
}
0