結果

問題 No.3281 Pacific White-sided Dolphin vs Monster
コンテスト
ユーザー matsukichi
提出日時 2025-09-26 22:10:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 310 ms / 2,000 ms
コード長 1,632 bytes
コンパイル時間 4,059 ms
コンパイル使用メモリ 253,356 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-03 17:36:26
合計ジャッジ時間 9,278 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<atcoder/all>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
#include <numeric>
#include <random>
#include<map>
#include<queue>
#include<deque>
#include <bitset>
#include<stack>
#include<set>
using namespace std;
using namespace atcoder;
#define int long long
using mint=modint998244353;
double pi=3.141592653589793128;
//cout << fixed << setprecision(10);
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for (int i=0;i<(n);++i)
#define prep(i,n) for (int i=1;i<=(n);++i)
#define ep(i,j,n) for (int i=j+1;i<=(n);++i)
long long INF = 900000000000000;
int mod=998244353;

signed main(){
   int v[62];v[0]=1;
   rep(i,61)v[i+1]=v[i]*2;
   int n;cin>>n;
   int h[n];
   rep(i,n)cin>>h[i];
   int l=1;int r=n+610;
   int u=n+1000;
   while(l<r){
     int mi=(l+r)/2;
     int mid=mi-1;
     //cout<<l<<" "<<r<<endl;
     //cout<<mid<<endl;
     priority_queue<int> pq;
     rep(i,n)pq.push(h[i]);
     
     if(l+1==r){
       mid=l;
       while(mid>=0 && !pq.empty()){
       int x=pq.top();pq.pop();
       if(mid>=61){mid--;continue;}
       if(v[mid]>=x){mid--;continue;}
       x-=v[mid];pq.push(x);mid--;
     }
     if(pq.empty()){
       r=l;break;
     }
     else{
       break;
     }
     }
     while(mid>=0 && !pq.empty()){
       int x=pq.top();pq.pop();
       if(mid>=60){mid--;continue;}
       if(v[mid]>=x){mid--;continue;}
       x-=v[mid];pq.push(x);mid--;
     }
    // cout<<mid<<" "<<l<<" "<<r<<endl;
     if(pq.empty()){
       r=mi;continue;
     }
     
       l=mi;
       //cout<<l<<" "<<mid<<endl;
       continue;
     
   }
   cout<<r+1;
}
0