#948611 (C++23) No.2603 Tone Correction

提出ソース

結果

問題	No.2603 Tone Correction
ユーザー	Re0denX
提出日時	2024-02-07 23:00:55
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	27 ms / 2,000 ms
コード長	5,450 bytes
コンパイル時間	2,988 ms
コンパイル使用メモリ	264,284 KB
実行使用メモリ	6,656 KB
最終ジャッジ日時	2024-02-07 23:01:04
合計ジャッジ時間	6,590 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	3 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	1 ms 6,548 KB
testcase_06	AC	3 ms 6,548 KB
testcase_07	AC	2 ms 6,548 KB
testcase_08	AC	2 ms 6,548 KB
testcase_09	AC	3 ms 6,548 KB
testcase_10	AC	2 ms 6,548 KB
testcase_11	AC	2 ms 6,548 KB
testcase_12	AC	3 ms 6,548 KB
testcase_13	AC	25 ms 6,656 KB
testcase_14	AC	24 ms 6,656 KB
testcase_15	AC	25 ms 6,656 KB
testcase_16	AC	25 ms 6,656 KB
testcase_17	AC	27 ms 6,656 KB
testcase_18	AC	24 ms 6,656 KB
testcase_19	AC	24 ms 6,656 KB
testcase_20	AC	24 ms 6,656 KB
testcase_21	AC	24 ms 6,656 KB
testcase_22	AC	23 ms 6,656 KB
testcase_23	AC	25 ms 6,656 KB
testcase_24	AC	24 ms 6,656 KB
testcase_25	AC	24 ms 6,656 KB
testcase_26	AC	23 ms 6,656 KB
testcase_27	AC	24 ms 6,656 KB
testcase_28	AC	24 ms 6,656 KB
testcase_29	AC	25 ms 6,656 KB
testcase_30	AC	22 ms 6,656 KB
testcase_31	AC	24 ms 6,656 KB
testcase_32	AC	26 ms 6,656 KB
testcase_33	AC	2 ms 6,548 KB
testcase_34	AC	15 ms 6,656 KB
testcase_35	AC	14 ms 6,656 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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
}

yukicoder

結果

テストケース

ソースコード