結果
問題 | No.2162 Copy and Paste 2 |
ユーザー | 👑 tute7627 |
提出日時 | 2022-12-13 03:18:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 39 ms / 7,000 ms |
コード長 | 9,492 bytes |
コンパイル時間 | 2,835 ms |
コンパイル使用メモリ | 208,820 KB |
実行使用メモリ | 16,688 KB |
最終ジャッジ日時 | 2024-04-24 15:33:35 |
合計ジャッジ時間 | 4,364 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 16 ms
11,672 KB |
testcase_07 | AC | 16 ms
11,576 KB |
testcase_08 | AC | 19 ms
11,416 KB |
testcase_09 | AC | 22 ms
11,592 KB |
testcase_10 | AC | 22 ms
11,488 KB |
testcase_11 | AC | 23 ms
11,668 KB |
testcase_12 | AC | 26 ms
11,584 KB |
testcase_13 | AC | 28 ms
11,588 KB |
testcase_14 | AC | 22 ms
11,756 KB |
testcase_15 | AC | 23 ms
11,528 KB |
testcase_16 | AC | 24 ms
11,752 KB |
testcase_17 | AC | 23 ms
11,612 KB |
testcase_18 | AC | 34 ms
12,604 KB |
testcase_19 | AC | 30 ms
11,760 KB |
testcase_20 | AC | 26 ms
11,464 KB |
testcase_21 | AC | 20 ms
11,416 KB |
testcase_22 | AC | 21 ms
11,544 KB |
testcase_23 | AC | 15 ms
11,408 KB |
testcase_24 | AC | 39 ms
16,688 KB |
testcase_25 | AC | 39 ms
16,544 KB |
testcase_26 | AC | 35 ms
13,472 KB |
testcase_27 | AC | 39 ms
16,684 KB |
testcase_28 | AC | 31 ms
13,976 KB |
ソースコード
//#define _GLIBCXX_DEBUG #include<bits/stdc++.h> using namespace std; #define endl '\n' #define lfs cout<<fixed<<setprecision(10) #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end()) #define spa << " " << #define fi first #define se second #define MP make_pair #define MT make_tuple #define PB push_back #define EB emplace_back #define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++) #define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 1e18; using P = pair<ll, ll>; template<typename T> using PQ = priority_queue<T>; template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>; template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;} template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;} ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});} void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;} void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;} void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;} template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;} template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);}; template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}}; template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;}; template<typename T>void debug(const vector<T>&v){debug(v,v.size());} template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());} template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;} template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;} template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;} template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;} template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;} template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1}; template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);} template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));} template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << p.first << " " << p.second;} template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){for(auto &z:v)os << z << " ";os<<"|"; return os;} template<typename T>void rearrange(vector<int>&ord, vector<T>&v){ auto tmp = v; for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]]; } template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){ rearrange(ord, head); rearrange(ord, tail...); } template<typename T> vector<int> ascend(const vector<T>&v){ vector<int>ord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);}); return ord; } template<typename T> vector<int> descend(const vector<T>&v){ vector<int>ord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);}); return ord; } template<typename T> vector<T> inv_perm(const vector<T>&ord){ vector<T>inv(ord.size()); for(int i=0;i<ord.size();i++)inv[ord[i]] = i; return inv; } ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;} ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;} ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;} ll modulo(ll n,ll d){return (n%d+d)%d;}; template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());} template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());} template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));}; template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());}; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int popcount(ll x){return __builtin_popcountll(x);}; int poplow(ll x){return __builtin_ctzll(x);}; int pophigh(ll x){return 63 - __builtin_clzll(x);}; template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;}; template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;}; template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;}; template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;}; ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;} ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;} ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;} template< typename T = int > struct edge { int to; T cost; int id; edge():id(-1){}; edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){} operator int() const { return to; } }; template<typename T> using Graph = vector<vector<edge<T>>>; template<typename T> Graph<T>revgraph(const Graph<T> &g){ Graph<T>ret(g.size()); for(int i=0;i<g.size();i++){ for(auto e:g[i]){ int to = e.to; e.to = i; ret[to].push_back(e); } } return ret; } template<typename T> Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){ Graph<T> ret(n); for(int es = 0; es < m; es++){ int u,v; T w=1; cin>>u>>v;u-=indexed,v-=indexed; if(weighted)cin>>w; ret[u].emplace_back(v,w,es); if(!directed)ret[v].emplace_back(u,w,es); } return ret; } template<typename T> Graph<T> readParent(int n,int indexed=1,bool directed=true){ Graph<T>ret(n); for(int i=1;i<n;i++){ int p;cin>>p; p-=indexed; ret[p].emplace_back(i); if(!directed)ret[i].emplace_back(p); } return ret; } vector<ll>z_algorithm(string s){ ll n = s.size(); vector<ll>ret(n,0); ret[0] = n; ll p = 1,len = 0; while(p < n){ while(p+len < n && s[len] == s[p+len])len++; ret[p] = len; if(len == 0){p++; continue;} ll k = 1; while(p+k < n && k+ret[k] < len)ret[p+k] = ret[k], k++; p += k, len -= k; } return ret; } struct FastSet{ using ull = unsigned long long; static constexpr uint B = 64; int n,lg; vector<vector<ull>> seg; FastSet(int _n) : n(_n){ do{ seg.push_back(vector<ull>((_n + B - 1) / B)); _n = (_n + B - 1) / B; } while (_n > 1); lg = seg.size(); } bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; } void set(int i) { for(int h = 0; h < lg; h++){ seg[h][i / B] |= 1ULL << (i % B); i /= B; } } void reset(int i) { for(int h = 0; h < lg; h++){ seg[h][i / B] &= ~(1ULL << (i % B)); if (seg[h][i / B]) break; i /= B; } } // x以上最小の要素 int next(int i){ for(int h = 0;h < lg; h++){ if (i / B == seg[h].size()) break; ull d = seg[h][i / B] >> (i % B); if (!d){ i = i / B + 1; continue; } // find i += __builtin_ctzll(d); for (int g = h - 1;g >= 0;g--){ i *= B; i += __builtin_ctzll(seg[g][i / B]); } return i; } return n; } // x未満最大の要素 int prev(int i){ i--; for (int h = 0;h < lg; h++){ if (i == -1) break; ull d = seg[h][i / B] << (63 - i % 64); if (!d){ i = i / B -1; continue; } // find i += (63 - __builtin_clzll(d)) - (B - 1); for(int g = h - 1;g >= 0;g--){ i *= B; i += (63 - __builtin_clzll(seg[g][i / B])); } return i; } return -1; } }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; string s;cin>>s; int n=s.size(); auto zv=z_algorithm(s); vector<vector<int>>pos(n+1); rep(i,0,n)pos[zv[i]].PB(i); FastSet st(n); rep(i,0,n)if(zv[i]>=1)st.set(i); vector<int>dp(n+1,1e9); dp[0]=0; rep(i,1,n+1){ chmin(dp[i],dp[i-1]+1); if(i==n){ cout<<dp[i]<<endl; break; } int now=dp[i]+1; int idx=i; while(1){ int nxt=st.next(idx); if(nxt==n)break; now+=nxt-idx+1; idx=nxt+i; chmin(dp[idx],now); } for(auto z:pos[i])st.reset(z); } return 0; }