結果
問題 | No.2603 Tone Correction |
ユーザー | Re0denX |
提出日時 | 2024-02-07 23:00:55 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 5,450 bytes |
コンパイル時間 | 3,468 ms |
コンパイル使用メモリ | 263,084 KB |
実行使用メモリ | 6,784 KB |
最終ジャッジ日時 | 2024-09-28 12:39:15 |
合計ジャッジ時間 | 7,164 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 30 ms
6,528 KB |
testcase_14 | AC | 29 ms
6,656 KB |
testcase_15 | AC | 31 ms
6,528 KB |
testcase_16 | AC | 28 ms
6,656 KB |
testcase_17 | AC | 28 ms
6,656 KB |
testcase_18 | AC | 29 ms
6,528 KB |
testcase_19 | AC | 29 ms
6,784 KB |
testcase_20 | AC | 28 ms
6,656 KB |
testcase_21 | AC | 29 ms
6,784 KB |
testcase_22 | AC | 29 ms
6,528 KB |
testcase_23 | AC | 26 ms
6,656 KB |
testcase_24 | AC | 26 ms
6,528 KB |
testcase_25 | AC | 26 ms
6,784 KB |
testcase_26 | AC | 26 ms
6,528 KB |
testcase_27 | AC | 27 ms
6,656 KB |
testcase_28 | AC | 26 ms
6,528 KB |
testcase_29 | AC | 26 ms
6,784 KB |
testcase_30 | AC | 27 ms
6,656 KB |
testcase_31 | AC | 26 ms
6,528 KB |
testcase_32 | AC | 26 ms
6,656 KB |
testcase_33 | AC | 3 ms
5,376 KB |
testcase_34 | AC | 16 ms
6,528 KB |
testcase_35 | AC | 15 ms
6,656 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #else #define debug(...) 42 #endif // LOCAL struct ChronoTimer { std::chrono::high_resolution_clock::time_point st; ChronoTimer() { reset(); } void reset() { st = std::chrono::high_resolution_clock::now(); } std::chrono::milliseconds::rep elapsed() { auto ed = std::chrono::high_resolution_clock::now(); return std::chrono::duration_cast<std::chrono::milliseconds>(ed - st) .count(); } }; /** * @brief Scanner(高速入力) */ struct Scanner { public: explicit Scanner(FILE *fp) : fp(fp) {} template <typename T, typename... E> void read(T &t, E &...e) { read_single(t); read(e...); } private: static constexpr size_t line_size = 1 << 16; static constexpr size_t int_digits = 20; char line[line_size + 1] = {}; FILE *fp = nullptr; char *st = line; char *ed = line; void read() {} static inline bool is_space(char c) { return c <= ' '; } void reread() { ptrdiff_t len = ed - st; memmove(line, st, len); char *tmp = line + len; ed = tmp + fread(tmp, 1, line_size - len, fp); *ed = 0; st = line; } void skip_space() { while (true) { if (st == ed) reread(); while (*st && is_space(*st)) ++st; if (st != ed) return; } } template <typename T, enable_if_t<is_integral<T>::value, int> = 0> void read_single(T &s) { skip_space(); if (st + int_digits >= ed) reread(); bool neg = false; if (is_signed<T>::value && *st == '-') { neg = true; ++st; } typename make_unsigned<T>::type y = *st++ - '0'; while (*st >= '0') { y = 10 * y + *st++ - '0'; } s = (neg ? -y : y); } template <typename T, enable_if_t<is_same<T, string>::value, int> = 0> void read_single(T &s) { s = ""; skip_space(); while (true) { char *base = st; while (*st && !is_space(*st)) ++st; s += string(base, st); if (st != ed) return; reread(); } } template <typename T> void read_single(vector<T> &s) { for (auto &d : s) read(d); } }; /** * @brief Printer(高速出力) */ struct Printer { public: explicit Printer(FILE *fp) : fp(fp) {} ~Printer() { flush(); } template <bool f = false, typename T, typename... E> void write(const T &t, const E &...e) { if (f) write_single(' '); write_single(t); write<true>(e...); } template <typename... T> void writeln(const T &...t) { write(t...); write_single('\n'); } void flush() { fwrite(line, 1, st - line, fp); st = line; } private: FILE *fp = nullptr; static constexpr size_t line_size = 1 << 16; static constexpr size_t int_digits = 20; char line[line_size + 1] = {}; char *st = line; template <bool f = false> void write() {} void write_single(const char &t) { if (st + 1 >= line + line_size) flush(); *st++ = t; } template <typename T, enable_if_t<is_integral<T>::value, int> = 0> void write_single(T s) { if (st + int_digits >= line + line_size) flush(); st += to_chars(st, st + int_digits, s).ptr - st; } void write_single(const string &s) { for (auto &c : s) write_single(c); } void write_single(const char *s) { while (*s != 0) write_single(*s++); } template <typename T> void write_single(const vector<T> &s) { for (size_t i = 0; i < s.size(); i++) { if (i) write_single(' '); write_single(s[i]); } } }; Scanner scanner = Scanner(stdin); Printer printer = Printer(stdout); void flush() { printer.flush(); } void print() { printer.write('\n'); } template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) { printer.write(head); if (sizeof...(Tail)) printer.write(' '); print(forward<Tail>(tail)...); } void read() {} template <class Head, class... Tail> void read(Head &head, Tail &...tail) { scanner.read(head); read(tail...); } #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ read(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define DBL(...) \ double __VA_ARGS__; \ read(__VA_ARGS__) #define VEC(type, name, size) \ vector<type> name(size); \ read(name) #define VV(type, name, h, w) \ vector<vector<type>> name(h, vector<type>(w)); \ read(name) int main(int, char **) { #ifdef LOCAL ChronoTimer chrono; freopen("/home/user/acm/competitve/src/input.txt", "r", stdin); freopen("/home/user/acm/competitve/src/output.txt", "w", stdout); #endif std::cout << fixed << setprecision(12); INT(N, M); VEC(int, A, N); VEC(int, B, N); std::vector<int> D(N + 2); for (auto i : views::iota(0, N)) { D[i + 1] = (B[i] - A[i] + M) % M; } std::vector<int> DD(N + 1); for (auto i : views::iota(0, N + 1)) { DD[i] = (D[i + 1] - D[i] + M) % M; } debug(DD); long long s = std::accumulate(DD.begin(), DD.end(), 0LL); long long overf = s / M; std::ranges::sort(DD, std::greater<int>()); for (auto i : views::iota(0, overf)) { DD[i] -= M; } debug(DD); auto res = DD | std::views::transform([](int x) { return std::abs(x); }); std::cout << std::accumulate(res.begin(), res.end(), 0LL) / 2 << "\n"; #ifdef LOCAL print("\nRunning Time:", chrono.elapsed(), "ms"); #endif }