結果

問題 No.3281 Pacific White-sided Dolphin vs Monster
ユーザー Today03
提出日時 2025-09-27 16:17:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,360 bytes
コンパイル時間 3,231 ms
コンパイル使用メモリ 287,816 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-09-27 16:17:18
合計ジャッジ時間 6,354 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
bool chmax(auto& a, auto b) { return a<b ? a=b, true : false; }
bool chmin(auto& a, auto b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif


/// @brief std::multiset ラッパー
template<typename T>
struct MultiSet:multiset<T> {
    using multiset<T>::multiset;
    T not_found;
    MultiSet()=default;

    /// @brief コンストラクタ
    /// @param not_found 指定の値が見つからなかったときに返す値
    MultiSet(T not_found=-1) {
        this->not_found=not_found;
    }

    /// @brief 最小値を返す
    T min() {
        if(this->empty())return not_found;
        return*this->begin();
    }

    /// @brief 最大値を返す
    T max() {
        if(this->empty()) return not_found;
        return*this->rbegin();
    }

    /// @brief 最小値を返し、削除する
    T pop_min() {
        if(this->empty()) return not_found;
        T ret=min();
        cnt[ret]--;
        this->erase(this->begin());
        return ret;
    }

    /// @brief 最大値を返し、削除する
    T pop_max() {
        if(this->empty()) return not_found;
        T ret=max();
        cnt[ret]--;
        this->erase(prev(this->end()));
        return ret;
    }  

    /// @brief x が含まれているか否かを返す
    bool contains(T x) {
        return this->find(x)!=this->end();
    }

    /// @brief x を削除する
    /// @brief x が含まれていたか否かを返す
    bool discard(T x) {
        auto itr=this->find(x);
        if(itr==this->end()) return false;
        cnt[*itr]--;
        this->erase(itr);
        return true;
    }

    /// @brief x より大きい最小の値を返す
    T gt(T x) {
        auto itr=this->upper_bound(x);
        if(itr==this->end()) return not_found;
        return*itr;
    }

    /// @brief x 以上の最小の値を返す
    T ge(T x) {
        auto itr=this->lower_bound(x);
        if(itr==this->end()) return not_found;
        return*itr;
    }

    /// @brief x 以下の最大の値を返す
    T le(T x) {
        auto itr=this->upper_bound(x);
        if(itr==this->begin()) return not_found;
        return*prev(itr);
    }

    /// @brief x 未満最大の値を返す
    T lt(T x) {
        auto itr=this->lower_bound(x);
        if(itr==this->begin()) return not_found;
        return*prev(itr);
    }

    /// @brief x の個数を返す
    int count(T x) {
        return cnt[x];
    }

private:
    map<T,int> cnt;
};

//----------------------------------------------------------

void solve() {
    int N; cin>>N;
    vector<ll> H(N); REP(i,N) cin>>H[i];

    MultiSet<ll> st(-1); REP(i,N) st.insert(H[i]);
    ll ans=0, p=1;
    while(!st.empty()) {
        ll x=st.le(p);
        debug(p,st);

        if(x!=-1) st.discard(x);
        else {
            x=st.max();
            st.discard(x);
            x-=p;
            st.insert(x);
        }

        p*=2; ans++;
        chmin(p,INFL);
    }

    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout<<fixed<<setprecision(15);
    int T=1; //cin>>T;
    while(T--) solve();
}
0