結果
問題 |
No.3221 Count Turns
|
ユーザー |
![]() |
提出日時 | 2025-08-01 22:50:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 5,974 bytes |
コンパイル時間 | 2,457 ms |
コンパイル使用メモリ | 188,352 KB |
実行使用メモリ | 16,112 KB |
最終ジャッジ日時 | 2025-08-01 22:50:27 |
合計ジャッジ時間 | 5,969 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#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]; vector<int> solve() { CompressedSequence comp{vector<int>(A, A + N)}; vector<vector<int>> pos(ssize(comp)); vector<long long> up(ssize(comp)), ti(ssize(comp)); for (int i = 0 ; i < ssize(comp) ; i++) { const int a = comp.inverse(i); ti[i] = (H + a - 1) / a; up[i] = (long long)a * ti[i]; } for (int i = 0 ; i < N ; i++) pos[comp.map(i)].push_back(i); using qt = tuple<long long, long long, int>; priority_queue<qt, vector<qt>, greater<qt>> que; for (int i = 0 ; i < ssize(comp) ; i++) que.push({ti[i], -up[i], i}); vector<int> C(N); while (T > 0 and ssize(que)) { auto [t, v, id] = que.top(); vector<pair<long long, int>> arr; vector<int> cur; while (ssize(que)) { auto [tt, vv, ii] = que.top(); if (t != tt) break; for (int x : pos[ii]) arr.push_back({vv, x}); cur.push_back(ii); que.pop(); } sort(arr.begin(), arr.end()); // for (auto [vv, ii] : arr) cout << '(' << vv << ',' << ii + 1 << ')'; // cout << endl; for (int i : arr | views::values) { // cout << i + 1 << " add" << endl; C[i]++; T--; if (T == 0) break; } for (int i : cur) { // cout << "push " << t + comp.inverse(i) << ' ' << -up[i] << ' ' << i + 1 << endl; que.push({t + ti[i], -up[i], i}); } } return C; } vector<int> naive() { vector<int> B(N), C(N); for (int i = 0 ; i < T ; i++) { while (*max_element(B.begin(), B.end()) < H) { for (int j = 0 ; j < N ; j++) B[j] += A[j]; } const int p = ranges::max_element(B) - B.begin(); B[p] = 0; C[p]++; } return C; } #include <random> int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); #ifdef DEBUG mt19937 mt{random_device{}()}; while (true) { cout << "--------------------------" << endl; N = mt() % 6 + 1; H = mt() % 20 + 1; T = mt() % 10 + 1; cout << N << ' ' << H << ' ' << T << endl; for (int i = 0 ; i < N ; i++) A[i] = mt() % H + 1; for (int i = 0 ; i < N ; i++) cout << A[i] << ' '; cout << endl; auto ans = naive(), my = solve(); if (ans != my) { for (auto i : ans) cout << i << ' '; cout << endl; cout << "but you ouput" << endl; for (auto i : my) cout << i << ' '; cout << endl; exit(0); } } #else cin >> N >> H >> T; for (int i = 0 ; i < N ; i++) cin >> A[i]; auto C = solve(); for (int i = 0 ; i < N ; i++) cout << C[i] << (i + 1 == N ? '\n' : ' '); #endif }