結果
| 問題 |
No.3269 Leq-K Partition
|
| コンテスト | |
| ユーザー |
ei1333333
|
| 提出日時 | 2025-09-22 23:59:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 373 ms / 6,000 ms |
| コード長 | 3,213 bytes |
| コンパイル時間 | 1,040 ms |
| コンパイル使用メモリ | 132,556 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-09-22 23:59:26 |
| 合計ジャッジ時間 | 8,083 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <random>
#include <ranges>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include<functional>
#include<cstring>
#include<utility>
#include<complex>
#include <cassert>
using namespace std;
using int64 = long long;
constexpr int64 infll = (1LL << 62) - 1;
constexpr int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < static_cast<int>(v.size()); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in: v) is >> in;
return is;
}
template<typename T1, typename T2>
bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template<typename T1, typename T2>
bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template<typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T &t, const V &v) {
t = v;
}
template<typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T &t, const V &v) {
for (auto &e: t) fill_v(e, v);
}
template<typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(std::forward<F>(f)) {
}
template<typename... Args>
decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template<typename F>
decltype(auto) MFP(F &&f) {
return FixPoint<F>{std::forward<F>(f)};
}
int main() {
int N;
cin >> N;
vector< int > A(N);
for (auto& a : A) {
cin >> a;
--a;
}
vector last(N, -1);
int t = 0;
auto solve = [&](int k) {
int d = 0, ret = 1;
for (const auto& a : A) {
if (last[a] != t) {
last[a] = t;
++d;
}
if (d > k) {
d = 1;
++t;
++ret;
last[a] = t;
}
}
++t;
return ret;
};
vector< int > ans(N + 2);
ans[0] = -inf;
ans[N + 1] = inf;
auto unos = MFP([&](auto unos, int l, int r) -> void {
if (l > r) {
return;
}
if (ans[l - 1] == ans[r + 1]) {
for (int k = l; k <= r; k++) {
ans[k] = ans[l - 1];
}
return;
}
int m = (l + r) / 2;
ans[m] = solve(m);
unos(l, m - 1);
unos(m + 1, r);
});
unos(1, N);
ans.erase(ans.begin());
ans.pop_back();
for (const auto& a : ans) cout << a << endl;
}
ei1333333