結果

問題 No.3221 Count Turns
ユーザー zawakasu
提出日時 2025-08-01 22:26:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,470 bytes
コンパイル時間 1,717 ms
コンパイル使用メモリ 144,492 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-01 22:26:57
合計ジャッジ時間 2,993 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
namespace ranges = std::ranges;
namespace views = std::views;
// #include "Src/Number/IntegerDivision.hpp"
// #include "Src/Utility/BinarySearch.hpp"


#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa

#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
#include <queue>
using namespace std;
int N, H, T, A[100010];
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> N >> H >> T;
    for (int i = 0 ; i < N ; i++) cin >> A[i];
    vector<int> app(N);
    for (int i = 0 ; i < N ; i++) app[i] = (H + A[i] - 1) / A[i];
    CompressedSequence comp{app};
    vector<vector<int>> pos(ssize(comp));
    for (int i = 0 ; i < N ; i++) pos[comp.map(i)].push_back(i);
    using qt = pair<long long, int>;
    priority_queue<qt, vector<qt>, greater<qt>> que;
    for (int i = 0 ; i < ssize(comp) ; i++) que.push({comp.inverse(i), i});
    vector<int> C(N);
    while (T > 0 and ssize(que)) {
        auto [t, id] = que.top();
        que.pop();
        vector<int> arr = pos[id];
        vector<int> cur{id};
        while (ssize(que) and que.top().first == t) {
            for (int x : pos[que.top().second]) {
                arr.push_back(x);
            }
            cur.push_back(que.top().second);
            que.pop();
        }
        sort(arr.begin(), arr.end());
        for (int i : arr) {
            C[i]++;
            T--;
            if (T == 0) break;
        }
        for (int i : cur) {
            que.push({t + comp.inverse(i), i});
        }
    }
    for (int i = 0 ; i < N ; i++) cout << C[i] << (i + 1 == N ? '\n' : ' ');
}
0