結果

問題 No.3269 Leq-K Partition
ユーザー 00 Sakuda
提出日時 2025-10-10 00:19:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,586 ms / 6,000 ms
コード長 1,130 bytes
コンパイル時間 4,602 ms
コンパイル使用メモリ 129,884 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-10 00:20:31
合計ジャッジ時間 32,442 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <math.h>
using namespace std;
using ll = long long;
int N;
vector<int> A;
int F(int K) {
	vector<int> CNT(N+1, 0);
	int res = 1;
	int it = 0;
	vector<int> value;
	while (it < N) {
		if (value.size() < K) {
			CNT[A[it]]++;
			if (CNT[A[it]] == 1) value.push_back(A[it]);
			it++;
			continue;	
		}
		if (CNT[A[it]] == 0) {
			res++;
			for (auto v : value) CNT[v] = 0;
			CNT[A[it]]++;
			value = {};
			value.push_back(A[it]);
			it++;
			continue;
		}
		CNT[A[it]]++;
		it++;
	}
	return res;
}
int main() {
	cin >> N;
	A.assign(N, 0);
	for (int i = 0;i < N;i++) cin >> A[i];
	int B = max(double(1), sqrt(N * log(N)));
	vector<int> R(N+1, -1);
	for (int i = 1;i <= B;i++) R[i] = F(i);
	int T = (N/B) + 2;
	for (int i = T;i >= 1;i--) {
		int ok = N;
		int ng = 0;
		while (ok-ng > 1) {
			int mid = (ok + ng) / 2;
			if (F(mid) <= i) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		for (int id = max(ok, B+1);id <= N;id++) R[id] = i;
	}
	for (int i = 1;i <= N;i++) cout << R[i] << endl;
}
0