結果

問題 No.2162 Copy and Paste 2
コンテスト
ユーザー vjudge1
提出日時 2025-01-06 23:44:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 7,000 ms
コード長 3,666 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 63,612 KB
実行使用メモリ 23,736 KB
最終ジャッジ日時 2025-01-06 23:44:51
合計ジャッジ時間 3,096 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* ??????????*/

#ifdef DEBUG
#include <iostream>
#include <cmath>
#include <ctime>

bool Mbe;
void _dihan();
#endif

#include <cstdio>
#include <cctype>
#include <cstring>
#include <numeric>
#include <algorithm>

typedef __int128_t i28;
typedef __int64_t i64;
using uit = __uint32_t;
using ull = __uint64_t;

template <typename T>
bool chkmx(T &x, T y) { return x < y ? x = y, true : false; }
template <typename T>
bool chkmn(T &x, T y) { return x > y ? x = y, true : false; }

namespace IO {

#define file(s) freopen(#s".in", "r", stdin), freopen(#s".out", "w", stdout)

constexpr int SIZE = 1 << 21;
char ibuf[SIZE], *p1 = ibuf, *p2 = ibuf, obuf[SIZE], *p3 = obuf;

#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++)
#define pc(ch) (p3 == obuf + SIZE && flush(), *p3++ = ch)
class Flush { public: ~Flush() { flush(); } } _;

auto chkChar = [](const char &c) -> bool { return c >= 'a' && c <= 'z'; };
template <typename T>
inline void read(T &x) {
   static char c;
   static bool f;

   x = 0, f = true;
   while (!isdigit(c = gc())) if (c == '-') f = false;

   while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
   f || (x = ~(x - 1), 0);
}
inline void read(char &c) {
   while (!chkChar(c = gc())) ;
}
inline void read(char *s) {
   static char c;

   while (!chkChar(c = gc())) ;

   while (chkChar(c)) *s++ = c, c = gc();
   *s = '\0';
}

template <typename T>
inline void write(T x) {
   static char stk[50]; static int top;

   x < 0 && (pc('-'), x = ~(x - 1), 1), top = 0;
   do stk[++top] = x % 10 ^ 48; while (x /= 10);

   while (top) pc(stk[top--]);
}
inline void write(char c) { pc(c); }
inline void write(char *s) { while (*s) pc(*s++); }
inline void write(const char *s) {
   for (int i = 0; *(s + i); ++i) pc(*(s + i));
}

template <typename T, typename ...Args>
inline void read(T &first, Args &...args) { read(first), read(args...); }
template <typename T, typename ...Args>
inline void write(T first, Args ...args) { write(first), write(args...); }

}
using namespace IO;

constexpr int N = 2e6 + 6;

char s[N];
int n;

int z[N];
void exKMP() {
   z[1] = n;

   for (int i = 2, l = 0, r = 0; i <= n; ++i) {
      if (i <= r && z[i - l + 1] < r - i + 1)
         z[i] = z[i - l + 1];
      else {
         z[i] = std::max(0, r - i + 1);

         while (i + z[i] <= n
             && s[1 + z[i]] == s[i + z[i]]) ++z[i];
      }

      if (chkmx(r, i + z[i] - 1)) l = i;
   }
}

int f[N], g[N];

class Disjoint {
 private:
   int _fa[N];

 public:
   void reset() {
      std::iota(_fa + 1, _fa + n + 2, 1);
   }

   int find(int x) {
      return x ^ _fa[x] ?
         _fa[x] = find(_fa[x]) : x;
   }
   void merge(int x, int y) {
      _fa[x] = y;
   }
} dsu;

int main() {
#ifdef DEBUG
   file(cur);
#endif

   read(s + 1), n = strlen(s + 1);

   exKMP();

   memset(f + 1, 0x3f, n * sizeof(int));
   memset(g + 1, 0x3f, n * sizeof(int));

   dsu.reset();

   for (int i = 1, mn = 0; i <= n; ++i) {
      mn = std::min(mn + 1, g[i]);

      f[i] = mn;

      for (int p = dsu.find(i + 1), c = 0;
               p <= n;
               p = dsu.find(p + 1)) {
         if (z[p] < i)
            dsu.merge(p, p + 1);
         else {
            chkmn(g[p + i - 1],
                  f[i] + 1 + p - i - c * (i - 1));

            ++c, p += i - 1;
         }
      }
   }

   write(f[n], '\n');

#ifdef DEBUG
   _dihan();
#endif
   return 0;
}

#ifdef DEBUG
bool Med;
void _dihan() {
   std::cerr << "Memory: " << abs(&Med - &Mbe) / 1048576.0 << " MB\n";
   std::cerr << "Time: " << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
}
#endif
0