結果
問題 | No.2114 01 Matching |
ユーザー | noshi91 |
提出日時 | 2022-10-28 23:09:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 597 ms / 5,000 ms |
コード長 | 5,408 bytes |
コンパイル時間 | 1,562 ms |
コンパイル使用メモリ | 107,708 KB |
実行使用メモリ | 54,644 KB |
最終ジャッジ日時 | 2023-08-16 02:48:32 |
合計ジャッジ時間 | 17,331 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 183 ms
12,580 KB |
testcase_03 | AC | 116 ms
14,048 KB |
testcase_04 | AC | 135 ms
18,420 KB |
testcase_05 | AC | 55 ms
6,444 KB |
testcase_06 | AC | 176 ms
11,992 KB |
testcase_07 | AC | 158 ms
6,708 KB |
testcase_08 | AC | 173 ms
13,104 KB |
testcase_09 | AC | 134 ms
7,484 KB |
testcase_10 | AC | 186 ms
10,340 KB |
testcase_11 | AC | 592 ms
54,644 KB |
testcase_12 | AC | 585 ms
54,424 KB |
testcase_13 | AC | 143 ms
14,936 KB |
testcase_14 | AC | 181 ms
18,872 KB |
testcase_15 | AC | 180 ms
17,392 KB |
testcase_16 | AC | 207 ms
16,092 KB |
testcase_17 | AC | 176 ms
12,008 KB |
testcase_18 | AC | 103 ms
9,992 KB |
testcase_19 | AC | 140 ms
15,104 KB |
testcase_20 | AC | 580 ms
54,600 KB |
testcase_21 | AC | 170 ms
15,816 KB |
testcase_22 | AC | 107 ms
6,928 KB |
testcase_23 | AC | 134 ms
11,188 KB |
testcase_24 | AC | 38 ms
4,768 KB |
testcase_25 | AC | 39 ms
5,992 KB |
testcase_26 | AC | 587 ms
54,508 KB |
testcase_27 | AC | 584 ms
54,528 KB |
testcase_28 | AC | 283 ms
31,628 KB |
testcase_29 | AC | 593 ms
54,568 KB |
testcase_30 | AC | 157 ms
7,028 KB |
testcase_31 | AC | 597 ms
54,524 KB |
testcase_32 | AC | 171 ms
9,272 KB |
testcase_33 | AC | 183 ms
12,312 KB |
testcase_34 | AC | 158 ms
6,520 KB |
testcase_35 | AC | 198 ms
24,168 KB |
testcase_36 | AC | 579 ms
54,492 KB |
testcase_37 | AC | 133 ms
8,912 KB |
testcase_38 | AC | 158 ms
6,784 KB |
testcase_39 | AC | 71 ms
6,052 KB |
testcase_40 | AC | 192 ms
23,684 KB |
testcase_41 | AC | 153 ms
7,996 KB |
testcase_42 | AC | 124 ms
9,492 KB |
testcase_43 | AC | 177 ms
12,732 KB |
testcase_44 | AC | 200 ms
16,904 KB |
testcase_45 | AC | 350 ms
54,584 KB |
testcase_46 | AC | 49 ms
5,204 KB |
testcase_47 | AC | 588 ms
54,588 KB |
testcase_48 | AC | 581 ms
54,424 KB |
testcase_49 | AC | 140 ms
14,920 KB |
testcase_50 | AC | 64 ms
5,024 KB |
testcase_51 | AC | 154 ms
6,688 KB |
testcase_52 | AC | 181 ms
17,764 KB |
ソースコード
#include <iostream> #include <map> #include <vector> //#define NDEBUG #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> #include <iostream> #include <utility> #include <vector> namespace n91 { using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept : i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct revrep { struct itr { usize i; constexpr itr(const usize i) noexcept : i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr revrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; template <class T> auto md_vec(const usize n, const T &value) { return std::vector<T>(n, value); } template <class... Args> auto md_vec(const usize n, Args... args) { return std::vector<decltype(md_vec(args...))>(n, md_vec(args...)); } template <class T> constexpr T difference(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; } template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; } template <class F> class rec_lambda { F f; public: rec_lambda(F &&f) : f(std::move(f)) {} template <class... Args> auto operator()(Args &&... args) const { return f(*this, std::forward<Args>(args)...); } }; template <class F> auto make_rec(F &&f) { return rec_lambda<F>(std::move(f)); } template <class T> T scan() { T ret; std::cin >> ret; return ret; } constexpr char eoln = '\n'; template <class T> T ceildiv(const T &l, const T &r) { return l / r + (l % r != 0 ? 1 : 0); } } // namespace n91 #include <deque> namespace n91 { void main_() { const auto solve = [](std::vector<int> lxt, std::vector<int> rxt) -> i64 { if (lxt.empty()) { return 0; } struct vtx { int type; // 0:a, 1:b i64 v; }; std::vector<vtx> vs; for (const auto e : lxt) { vs.push_back({0, e}); } for (const auto e : rxt) { vs.push_back({1, e}); } std::sort(vs.begin(), vs.end(), [](const auto &l, const auto &r) { return l.v < r.v; }); struct aque { std::deque<std::pair<i64, i64>> v; i64 a; aque() : v(), a(0) {} void push_front(i64 x, i64 l) { v.push_front({x - a, l}); } void push_back(i64 x, i64 l) { v.push_back({x - a, l}); } bool empty() { return v.empty(); } i64 front() { return v.front().first + a; } std::pair<i64, i64> pop_front() { auto ret = v.front(); v.pop_front(); return {ret.first + a, ret.second}; } std::pair<i64, i64> pop_back() { auto ret = v.back(); v.pop_back(); return {ret.first + a, ret.second}; } void add(i64 x) { a += x; } }; i64 min_pos = 0; i64 min_val = 0; aque m, r; r.push_back(1e10, 3e5); const auto shift = [&]() { auto [s, len] = m.pop_front(); min_pos += len; min_val += s * len; }; i64 prev = 0; for (const auto &[type, x] : vs) { const i64 dif = (x - prev); min_val += dif * (-min_pos); m.add(-dif); r.add(dif); while (!m.empty() && m.front() < 0) { shift(); } if (type == 0) { min_pos -= 1; assert(!r.empty()); auto [s, len] = r.pop_front(); m.push_back(s, 1); if (len - 1 != 0) { r.push_front(s, len - 1); } } else { m.push_front(0, 1); i64 m_r = 1; while (m_r != 0) { assert(!m.empty()); auto [s, len] = m.pop_back(); const i64 t = std::min(len, m_r); r.push_front(s, t); m_r -= t; if (len - t != 0) { m.push_back(s, len - t); } } } prev = x; } while (!m.empty()) { shift(); } return min_val; }; int N, M, K; std::cin >> N >> M >> K; std::vector<int> B(N), R(M); for (auto &e : B) { std::cin >> e; } for (auto &e : R) { std::cin >> e; } if (N > M) { std::swap(N, M); std::swap(B, R); } std::map<int, std::pair<std::vector<int>, std::vector<int>>> map; for (const auto e : B) { map[e % K].first.push_back(e / K); } for (const auto e : R) { map[e % K].second.push_back(e / K); } long long ans = 0; for (auto &[key, val] : map) { auto &[l, r] = val; if (l.size() > r.size()) { std::cout << "-1\n"; return; } ans += solve(l, r); } std::cout << ans << eoln; } } // namespace n91 int main() { n91::main_(); return 0; }