#1122955 (C++17) No.3281 Pacific White-sided Dolphin vs Monster

• 問題: No.3281 Pacific White-sided Dolphin vs Monster
• ユーザー: 回転
• 提出日時: 2025-09-26 22:20:40
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 11,472 bytes
• コンパイル時間: 2,699 ms
• コンパイル使用メモリ: 217,428 KB
• 実行使用メモリ: 7,720 KB
• 最終ジャッジ日時: 2025-09-26 22:20:50
• 合計ジャッジ時間: 9,379 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 49 WA * 1

ソースコード

/* Original Python code (kept as required by AtCoder rules)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right

class SortedMultiset():
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        n = self.size = len(a)
        if any(a[i] > a[i + 1] for i in range(n - 1)):
            a.sort()
        num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
        self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]

    def __iter__(self):
        for i in self.a:
            for j in i: yield j

    def __reversed__(self):
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __eq__(self, other) -> bool:
        return list(self) == list(other)
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _position(self, x):
        "return the bucket, index of the bucket and position in which x should be. self must not be empty."
        for i, a in enumerate(self.a):
            if x <= a[-1]: break
        return (a, i, bisect_left(a, x))

    def __contains__(self, x) -> bool:
        if self.size == 0: return False
        a, _, i = self._position(x)
        return i != len(a) and a[i] == x

    def count(self, x) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a, b, i = self._position(x)
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.SPLIT_RATIO:
            mid = len(a) >> 1
            self.a[b:b+1] = [a[:mid], a[mid:]]
    
    def _pop(self, a, b: int, i: int):
        ans = a.pop(i)
        self.size -= 1
        if not a: del self.a[b]
        return ans

    def discard(self, x) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a, b, i = self._position(x)
        if i == len(a) or a[i] != x: return False
        self._pop(a, b, i)
        return True

    def lt(self, x):
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x):
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x):
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x):
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, i: int):
        "Return the i-th element."
        if i < 0:
            for a in reversed(self.a):
                i += len(a)
                if i >= 0: return a[i]
        else:
            for a in self.a:
                if i < len(a): return a[i]
                i -= len(a)
        raise IndexError
    
    def pop(self, i: int = -1):
        "Pop and return the i-th element."
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._pop(a, ~b, i)
        else:
            for b, a in enumerate(self.a):
                if i < len(a): return self._pop(a, b, i)
                i -= len(a)
        raise IndexError

    def index(self, x) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans

N = int(input())
H = list(map(int,input().split()))
H.sort()
SUM = sum(H)

def check(now,having):
    if(len(now) > len(having)):return False
    if(sum(now) > sum(having)):return False
    
    for i in list(having)[::-1]:
        if(not now):return True
        v = now.pop()
        if(v > i):now.add(v-i)
    
    return len(now) == 0

for ans in range(N,N+61):
    if(N < 60 and 2**ans < SUM):continue
    now = SortedMultiset(H)
    p = 1
    having = SortedMultiset([])
    for _ in range(ans):
        place = now.index_right(p) - 1
        if(place == -1):
            having.add(p)
        else:
            now.pop(place)
        p *= 2

    if(check(now,having)):
        print(ans)
        exit()
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SortedMultiset {
    static const int BUCKET_RATIO = 16;
    static const int SPLIT_RATIO = 24;
    vector<vector<ll>> a;
    size_t sz;

    SortedMultiset(): a(), sz(0) {}
    SortedMultiset(const vector<ll>& v) {
        vector<ll> arr = v;
        sz = arr.size();
        if (sz == 0) {
            a.clear();
            return;
        }
        bool sorted = true;
        for (size_t i = 1; i < arr.size(); ++i) {
            if (arr[i-1] > arr[i]) { sorted = false; break; }
        }
        if (!sorted) sort(arr.begin(), arr.end());
        size_t n = arr.size();
        size_t num_bucket = (size_t)ceil(sqrt((double)max<size_t>(n,1) / (double)BUCKET_RATIO));
        if (num_bucket == 0) num_bucket = 1;
        a.clear();
        a.reserve(num_bucket);
        for (size_t i = 0; i < num_bucket; ++i) {
            size_t l = n * i / num_bucket;
            size_t r = n * (i + 1) / num_bucket;
            if (l < r) a.emplace_back(arr.begin() + l, arr.begin() + r);
        }
    }

    bool empty() const { return sz == 0; }
    size_t size() const { return sz; }

    pair<int,int> _position(ll x) {
        for (int i = 0; i < (int)a.size(); ++i) {
            if (!a[i].empty() && x <= a[i].back()) {
                auto it = lower_bound(a[i].begin(), a[i].end(), x);
                return {i, (int)distance(a[i].begin(), it)};
            }
        }
        if (!a.empty()) {
            auto it = lower_bound(a.back().begin(), a.back().end(), x);
            return {(int)a.size()-1, (int)distance(a.back().begin(), it)};
        }
        return {-1, 0};
    }

    void add(ll x) {
        if (sz == 0) {
            a = vector<vector<ll>>(1, vector<ll>(1, x));
            sz = 1;
            return;
        }
        auto pos = _position(x);
        int b = pos.first;
        int i = pos.second;
        if (b == -1) {
            a.emplace_back();
            a.back().push_back(x);
        } else {
            a[b].insert(a[b].begin() + i, x);
        }
        ++sz;
        if (b >= 0 && (int)a[b].size() > (int)a.size() * SPLIT_RATIO) {
            int mid = (int)a[b].size() >> 1;
            vector<ll> left(a[b].begin(), a[b].begin() + mid);
            vector<ll> right(a[b].begin() + mid, a[b].end());
            a.erase(a.begin() + b);
            a.insert(a.begin() + b, right);
            a.insert(a.begin() + b, left);
        }
    }

    ll _pop_from_bucket(int b, int idx) {
        ll ans = a[b][idx];
        a[b].erase(a[b].begin() + idx);
        --sz;
        if (a[b].empty()) a.erase(a.begin() + b);
        return ans;
    }

    ll pop(long long i = -1) {
        if (sz == 0) throw out_of_range("pop from empty SortedMultiset");
        long long idx = i;
        if (idx < 0) idx += (long long)sz;
        if (idx < 0 || (size_t)idx >= sz) throw out_of_range("pop index out of range");
        long long cur = idx;
        for (int b = 0; b < (int)a.size(); ++b) {
            if (cur < (long long)a[b].size()) {
                return _pop_from_bucket(b, (int)cur);
            }
            cur -= (long long)a[b].size();
        }
        throw out_of_range("unreachable pop");
    }

    long long index(ll x) const {
        long long ans = 0;
        for (const auto& bucket : a) {
            if (bucket.empty()) continue;
            if (bucket.back() >= x) {
                auto it = lower_bound(bucket.begin(), bucket.end(), x);
                ans += (long long)distance(bucket.begin(), it);
                return ans;
            }
            ans += (long long)bucket.size();
        }
        return ans;
    }

    long long index_right(ll x) const {
        long long ans = 0;
        for (const auto& bucket : a) {
            if (bucket.empty()) continue;
            if (bucket.back() > x) {
                auto it = upper_bound(bucket.begin(), bucket.end(), x);
                ans += (long long)distance(bucket.begin(), it);
                return ans;
            }
            ans += (long long)bucket.size();
        }
        return ans;
    }

    vector<ll> to_list() const {
        vector<ll> res;
        res.reserve(sz);
        for (const auto& bucket : a)
            for (const auto& v : bucket) res.push_back(v);
        return res;
    }

    ll sum_all() const {
        long long s = 0;
        for (const auto& bucket : a)
            for (const auto& v : bucket) s += v;
        return s;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<ll> H;
    H.reserve(N);
    for (int i = 0; i < N; ++i) {
        long long x; cin >> x;
        H.push_back(x);
    }
    sort(H.begin(), H.end());
    long long SUM = 0;
    for (auto &v : H) SUM += v;

    auto check = [&](SortedMultiset now, const SortedMultiset& having)->bool {
        if (now.size() > having.size()) return false;
        if (now.sum_all() > having.sum_all()) return false;
        vector<ll> hv = having.to_list();
        for (auto it = hv.rbegin(); it != hv.rend(); ++it) {
            if (now.size() == 0) return true;
            ll v = now.pop(); // pop last
            if (v > *it) {
                ll diff = v - *it;
                now.add(diff);
            }
        }
        return now.size() == 0;
    };

    for (int ans = N; ans <= N + 60; ++ans) {
        if (N < 60) {
            if (ans < 63) {
                long long pow2 = (1LL << ans);
                if (pow2 < SUM) continue;
            } else {
                // 2^ans is >= 2^63 > LLONG_MAX >= SUM, so 2^ans < SUM is false -> do nothing
            }
        }
        SortedMultiset now(H);
        long long p = 1;
        SortedMultiset having;
        for (int i = 0; i < ans; ++i) {
            long long place = now.index_right(p) - 1;
            if (place == -1) {
                having.add(p);
            } else {
                now.pop(place);
            }
            // shift p by 1, watch overflow but user requested long long
            if (p > (LLONG_MAX / 2)) p = LLONG_MAX; else p <<= 1;
        }
        if (check(now, having)) {
            cout << ans << '\n';
            return 0;
        }
    }
    return 0;
}