結果
問題 | No.2162 Copy and Paste 2 |
ユーザー | 👑 Nachia |
提出日時 | 2022-12-13 23:41:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 7,000 ms |
コード長 | 5,224 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 107,456 KB |
実行使用メモリ | 8,888 KB |
最終ジャッジ日時 | 2024-11-15 03:05:27 |
合計ジャッジ時間 | 3,444 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 14 ms
8,868 KB |
testcase_07 | AC | 15 ms
8,884 KB |
testcase_08 | AC | 20 ms
8,880 KB |
testcase_09 | AC | 24 ms
8,876 KB |
testcase_10 | AC | 25 ms
8,880 KB |
testcase_11 | AC | 26 ms
8,752 KB |
testcase_12 | AC | 28 ms
8,880 KB |
testcase_13 | AC | 32 ms
8,888 KB |
testcase_14 | AC | 23 ms
8,760 KB |
testcase_15 | AC | 25 ms
8,744 KB |
testcase_16 | AC | 25 ms
8,744 KB |
testcase_17 | AC | 25 ms
8,884 KB |
testcase_18 | AC | 29 ms
8,756 KB |
testcase_19 | AC | 28 ms
8,752 KB |
testcase_20 | AC | 28 ms
8,888 KB |
testcase_21 | AC | 22 ms
8,888 KB |
testcase_22 | AC | 23 ms
8,752 KB |
testcase_23 | AC | 14 ms
8,884 KB |
testcase_24 | AC | 29 ms
8,760 KB |
testcase_25 | AC | 29 ms
8,752 KB |
testcase_26 | AC | 30 ms
8,884 KB |
testcase_27 | AC | 29 ms
8,756 KB |
testcase_28 | AC | 28 ms
8,756 KB |
ソースコード
#line 1 "Main.cpp" #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <atcoder/modint> #include <atcoder/string> #include <atcoder/dsu> #line 5 "nachia\\array\\csr-array.hpp" namespace nachia{ template<class Elem> class CsrArray{ public: struct ListRange{ using iterator = typename std::vector<Elem>::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector<Elem>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector<Elem> m_list; std::vector<int> m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){ CsrArray res; res.m_n = n; std::vector<int> buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 1 "nachia\\misc\\bit-operations.hpp" #line 4 "nachia\\misc\\bit-operations.hpp" namespace nachia{ int Popcount(unsigned long long c) noexcept { #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/257)) >> 56; return c; #endif } // please ensure x != 0 int MsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return 63 - __builtin_clzll(x); #else int res = 0; for(int d=32; d>=0; d>>=1) if(x >> d){ res |= d; x >>= d; } return res; #endif } // please ensure x != 0 int LsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return __builtin_ctzll(x); #else return msb_idx(x & -x); #endif } } #line 11 "Main.cpp" using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; struct DecrementalNeighborQuery{ int n; int b; std::vector<unsigned long long> X; atcoder::dsu Y; std::vector<int> dsuTrans; DecrementalNeighborQuery(int _n) : n(_n+2), b(n/64+2), X(b, ~0ull), Y(b), dsuTrans(b) { for(int i=0; i<b; i++) dsuTrans[i] = i; } int smallQ(int c, int d) const noexcept { auto z = X[c] & ((~0ull) << d); return z ? c*64 + nachia::LsbIndex(z) : -1; } int largeQ(int c) noexcept { return dsuTrans[Y.leader(c)]; } void dec(int i){ i++; int c = i/64, d = i%64; X[c] &= ~(1ull << d); if(X[c] == 0){ int h = largeQ(c+1); dsuTrans[Y.merge(c, c+1)] = h; } } int queryRight(int i){ i++; int c = i/64, d = i%64; int x = smallQ(c, d); if(x >= 0) return x-1; c = largeQ(c+1); d = 0; return smallQ(c, d)-1; } }; int main(){ string S; cin >> S; auto Z = atcoder::z_algorithm(S); int n = S.size(); vector<pair<int,int>> pairs(n); rep(i,n) pairs[i] = { Z[i], i }; auto csr = nachia::CsrArray<int>::Construct(n+1, pairs); auto Q = DecrementalNeighborQuery(n); vector<int> dp(n+1); rep(i,n+1) dp[i] = i; for(int x=1; x<=n; x++){ for(int c : csr[x-1]){ Q.dec(c); } dp[x] = min(dp[x], dp[x-1] + 1); int p = x, t = dp[x] + 1; while(p < n){ int nx = Q.queryRight(p); if(nx >= n) break; t += nx - p + 1; p = nx + x; dp[p] = min(dp[p], t); } } cout << dp[n] << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;