結果

問題 No.3780 Erase and Mex
コンテスト
ユーザー akasinn
提出日時 2026-10-30 23:35:44
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,896 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 867 ms
コンパイル使用メモリ 146,104 KB
実行使用メモリ 31,616 KB
最終ジャッジ日時 2026-10-30 23:36:19
合計ジャッジ時間 33,044 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//yukicoder No.3779
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision ?
#include <numeric>
#include <iterator>
#include <random>
#include <assert.h>
//#include <stdlib.h>
using namespace std;
typedef int64_t ll;

//出力
void print(bool b){
  if(b)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return;
}
void print(vector<int> V){
  for(auto i=V.begin();i!=V.end();i++)cout<<*i<<(next(i)==V.end() ? "" : " ");
  cout<<endl;
  return;
}
void print(vector<vector<int>> V){
  for(auto &v:V)print(v);
  return;
}
//ここまでがテンプレーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

bool make_(int a,multiset<int> &S){
  //cerr<<"  make_ is called a="<<a<<" S=";
  //for(int s:S)cerr<<s<<" ";
  //cerr<<endl;
  if(a==0){
    if(S.size()==0)return false;
    auto itr=S.end();
    itr--;
    if((*itr))
    S.erase(itr);
    S.insert(0);
    return true;
  }
  for(int i=a-1;i>=0;i--){
    if(!S.count(i)){
      bool b=make_(i,S);
      if(!b)return false;
    }
    auto itr=S.find(i);
    //cerr<<"  erase "<<i<<endl;
    S.erase(itr);
  }
  S.insert(a);
  return true;
}



bool solve(int ans,multiset<int> S){
  //cerr<<"solve is called ans="<<ans<<endl;
  for(int i=ans-1;i>=0;i--){
    //cerr<<" i="<<i<<endl;
    if(!S.count(i)){//Sにiが含まれないので、作ろうとする
      bool b=make_(i,S);
      if(!b)return false;//作れなかったらおしまい
    }
  }
  return true;
}


int main(){//main関数ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    multiset<int> S;
    for(int i=0;i<n;i++){
      int a; cin>>a;
      S.insert(a);
    }
    if(S.size()==1){
      cout<<max(*S.begin(),1)<<endl;
      continue;
    }
    //解のにぶたんで解く
    int ok=1,ng=S.size()+2;
    while(ok+1<ng){
      int middle=(ok+ng)/2;
      bool b=solve(middle,S);
      //cerr<<"solve "<<middle<<" = "<<b<<endl;
      if(b)ok=middle;
      else ng=middle;
    }
    cout<<ok<<endl;
  }
  return 0;
}
0