結果

問題 No.3269 Leq-K Partition
ユーザー memin
提出日時 2025-09-12 23:01:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,195 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 202,260 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-12 23:44:54
合計ジャッジ時間 70,314 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 17 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll = long long;
using pp = pair<int,int>;
#define rep(i, n) for (i = 0; (i) < (n); ++(i))
#define reps(i, a, n) for (i = (a); (i) < (n); ++(i))
#define rrep(i, n) for (i = (n-1); (i) >= (0); --(i))
#define all(a) (a).begin(), (a).end()
#define oor(a,b,h,w) (a<0||a>=h||b<0||b>=w)//out of range
#define fi first
#define se second
#define mkpr(a,b) make_pair(a,b)
#define mktpl(a,b,c) make_tuple(a,b,c)
#define fixp(a) fixed<<setprecision(a) //小数点以下指定
vector<int> dx={1,0,-1,0};//{1,1,0,-1,-1,-1,0,1};
vector<int> dy={0,-1,0,1};//{0,-1,-1,-1,0,1,1,1};
//ll keta_calc(ll x){ll ans=0;while(x){x/=10;ans++;}return ans;}
//ll powll(ll x,ll y){ll ans=1;while(y){ans*=x;y--;}return ans;}
//alias g++='g++ -std=c++17'
#define chmin(a,b) a=min(a,(b))
#define chmax(a,b) a=max(a,(b))
int n;
bool solve(int mid, int b , vector<int> &a){
    int i=0,j,k;
    vector<bool> f(n,false);
    while(i<n){
        j = i;
        int cnt = 0;
        while(j<n){
            if(f[ a[j] ] == false){
                cnt++;
                if(cnt > mid){
                    break;
                }
                f[ a[j] ] = true;
            }
            if(cnt > mid){
                break;
            }
            j++;
        }
        reps(k,i,j){
            f[a[k]] = false;
        }
        b--;
        i=j;
        if(b==0)break;
    }
    if(i >= n){
        return true;
    }else{
        return false;
    }
}
int main(){
    int i=0,j=0,k;
    

    cin >> n ;
    vector<int> a(n),b;
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    //分割数
    b.push_back(n+1);
    rep(i,sqrt(n)+1){
        int ok=n;int ng=0;
        // 種類数
        while(abs(ok-ng)>1){
            int mid = (ok+ng)/2;
            if(solve(mid,i+1, a)){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        b.push_back(ok);
    }
    // rep(i,b.size()){
    //     cout << b[i] << " ";
    // }cout << endl;

    int ki;
    rep(ki,n){
        vector<bool> f(n,false);
        int z = 0;
        i=0;
        while(i<n){
            j = i;
            int cnt = 0;
            while(j<n){
                if(f[ a[j] ] == false){
                    cnt++;
                    if(cnt > ki+1){
                        break;
                    }
                    f[ a[j] ] = true;
                }
                if(cnt > ki+1){
                    break;
                }
                j++;
            }
            reps(k,i,j){
                f[a[k]] = false;
            }
            i=j;
            z++;
        }
        cout << z << "\n";
        if(z <= b.size()){
            break;
        }
    }
    ki++;ki++;
    rrep(i,b.size()-1){
        // cout << ki << " " << b[i] << endl;
        reps(j,ki,b[i]){
            cout << i+1 << "\n";
        }
        ki = b[i];
    }
    //sort(aitem.begin(),aitem.end(),
    //[](const vector<int> &alpha,const vector<int> &beta){return alpha[1] < beta[1];});
    
    // cout << n << endl ;

    //if(flag==0)printf("Yes\n");
    //else printf("No\n");

    return 0;
}
0