結果

問題 No.3780 Erase and Mex
コンテスト
ユーザー akua
提出日時 2026-11-06 05:27:59
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,694 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,320 ms
コンパイル使用メモリ 220,356 KB
実行使用メモリ 9,920 KB
最終ジャッジ日時 2026-11-06 05:28:07
合計ジャッジ時間 5,128 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define repi(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define arr(x) (x).rbegin(),(x).rend()
template<typename T,typename S> bool chmin(T&a,const S&b){
    return a>b?a=b,1:0;
}
template<typename T,typename S> bool chmax(T&a,const S&b){
    return a<b?a=b,1:0;
}
using vi=vector<int>;
using P=pair<ll,ll>;
using vvi=vector<vi>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vp=vector<P>;
using i128=__int128_t;
#define sz(a) (ll)(size(a))
const ll inf=2e18;

void solve(int test){
    int n;cin >> n;
    vi a(n);
    rep(i,n)cin >> a[i];
    if(n==1){
        cout << a[0] << endl;
        return;
    }
    vll cnt(n);
    auto f=[&](int wj){
        rep(i,n)cnt[i]=0;
        rep(i,n){
            if(a[i]>=wj)cnt[0]++;
            else cnt[a[i]]++;
        }
        ll x=1;
        for(int i=wj-1; i>=0; i--){
            /*
            if(wj==5){
                cout<< i << " " << x << " "<< cnt[i] << endl;
            }
            */
            if(i==0){
                if(cnt[i]>=x)return true;
                else return false;
            }
            if(x>n){
                return false;
            }
            if(cnt[i]>=x){
                cnt[0]+=cnt[i]-x;
            }
            else {
                x+=x-cnt[i];
            }
        }
        return true;
    };
    int ac=0,wa=n+1;
    while(wa-ac>1){
        int wj=(wa+ac)/2;
        if(f(wj))ac=wj;
        else wa=wj;
    }
    cout << ac << endl;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;cin>> t;
    rep(test,t)solve(test);
}
0