Submission #7528479


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

void zalgo(string &S, function<void(int, int)> update) {
    vi A(sz(S));
    A[0] = S.size();
    update(0, A[0]);
    int i = 1, j = 0;
    while (i < S.size()) {
        while (i+j < S.size() && S[j] == S[i+j]) ++j;
        A[i] = j;
        update(i, A[i]);
        if (j == 0) {
            ++i; continue;
        }
        int k = 1;
        while (i+k < S.size() && k+A[k] < j) {
            A[i+k] = A[k];
            update(i+k, A[k]);
            ++k;
        }
        i += k; j -= k;
    }
}
signed main() {
    int N;
    cin >> N;
    string S;
    cin >> S;

    int ans = 0;
    rep(i, 0, N) {
        auto t = S.substr(i);
        zalgo(t, [&](int i, int v) {
            if (v <= i) {
                chmax(ans, v);
            }
        });
    }
    cout << ans << endl;
    return (0^_^0);
}

Submission Info

Submission Time
Task E - Who Says a Pun?
User algon
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2489 Byte
Status AC
Exec Time 117 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 70
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 01-handmade-12, 02-binary-13, 02-binary-14, 02-binary-15, 02-binary-16, 02-binary-17, 02-binary-18, 02-binary-19, 02-binary-20, 02-binary-21, 02-binary-22, 02-binary-23, 03-BigRandom-24, 03-BigRandom-25, 03-BigRandom-26, 03-BigRandom-27, 03-BigRandom-28, 03-BigRandom-29, 03-BigRandom-30, 03-BigRandom-31, 03-BigRandom-32, 03-BigRandom-33, 03-BigRandom-34, 03-BigRandom-35, 03-BigRandom-36, 03-BigRandom-37, 03-BigRandom-38, 03-BigRandom-39, 03-BigRandom-40, 03-BigRandom-41, 03-BigRandom-42, 03-BigRandom-43, 03-BigRandom-44, 03-BigRandom-45, 03-BigRandom-46, 03-BigRandom-47, 03-BigRandom-48, 03-BigRandom-49, 03-BigRandom-50, 03-BigRandom-51, 03-BigRandom-52, 03-BigRandom-53, 03-BigRandom-54, 04-zero-55, 04-zero-56, 05-AllRandom-57, 05-AllRandom-58, 05-AllRandom-59, 05-AllRandom-60, 05-AllRandom-61, 05-AllRandom-62, 05-AllRandom-63, 05-AllRandom-64, 05-AllRandom-65, 05-AllRandom-66, 05-AllRandom-67, 05-AllRandom-68, 05-AllRandom-69
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 89 ms 384 KB
01-handmade-04 AC 111 ms 384 KB
01-handmade-05 AC 80 ms 384 KB
01-handmade-06 AC 80 ms 384 KB
01-handmade-07 AC 80 ms 384 KB
01-handmade-08 AC 66 ms 256 KB
01-handmade-09 AC 80 ms 384 KB
01-handmade-10 AC 109 ms 256 KB
01-handmade-11 AC 98 ms 384 KB
01-handmade-12 AC 98 ms 384 KB
02-binary-13 AC 86 ms 256 KB
02-binary-14 AC 102 ms 256 KB
02-binary-15 AC 80 ms 256 KB
02-binary-16 AC 117 ms 256 KB
02-binary-17 AC 117 ms 256 KB
02-binary-18 AC 102 ms 256 KB
02-binary-19 AC 63 ms 256 KB
02-binary-20 AC 75 ms 256 KB
02-binary-21 AC 69 ms 256 KB
02-binary-22 AC 66 ms 256 KB
02-binary-23 AC 58 ms 256 KB
03-BigRandom-24 AC 68 ms 256 KB
03-BigRandom-25 AC 68 ms 256 KB
03-BigRandom-26 AC 66 ms 256 KB
03-BigRandom-27 AC 81 ms 256 KB
03-BigRandom-28 AC 74 ms 256 KB
03-BigRandom-29 AC 78 ms 256 KB
03-BigRandom-30 AC 75 ms 384 KB
03-BigRandom-31 AC 74 ms 256 KB
03-BigRandom-32 AC 81 ms 256 KB
03-BigRandom-33 AC 70 ms 256 KB
03-BigRandom-34 AC 75 ms 256 KB
03-BigRandom-35 AC 67 ms 256 KB
03-BigRandom-36 AC 80 ms 256 KB
03-BigRandom-37 AC 73 ms 256 KB
03-BigRandom-38 AC 68 ms 256 KB
03-BigRandom-39 AC 76 ms 384 KB
03-BigRandom-40 AC 72 ms 256 KB
03-BigRandom-41 AC 76 ms 256 KB
03-BigRandom-42 AC 73 ms 256 KB
03-BigRandom-43 AC 68 ms 256 KB
03-BigRandom-44 AC 71 ms 256 KB
03-BigRandom-45 AC 80 ms 384 KB
03-BigRandom-46 AC 67 ms 256 KB
03-BigRandom-47 AC 81 ms 256 KB
03-BigRandom-48 AC 70 ms 256 KB
03-BigRandom-49 AC 72 ms 256 KB
03-BigRandom-50 AC 82 ms 256 KB
03-BigRandom-51 AC 75 ms 256 KB
03-BigRandom-52 AC 79 ms 384 KB
03-BigRandom-53 AC 80 ms 256 KB
03-BigRandom-54 AC 77 ms 384 KB
04-zero-55 AC 1 ms 256 KB
04-zero-56 AC 1 ms 256 KB
05-AllRandom-57 AC 82 ms 384 KB
05-AllRandom-58 AC 75 ms 256 KB
05-AllRandom-59 AC 84 ms 256 KB
05-AllRandom-60 AC 80 ms 384 KB
05-AllRandom-61 AC 79 ms 384 KB
05-AllRandom-62 AC 78 ms 384 KB
05-AllRandom-63 AC 74 ms 256 KB
05-AllRandom-64 AC 74 ms 256 KB
05-AllRandom-65 AC 77 ms 384 KB
05-AllRandom-66 AC 78 ms 256 KB
05-AllRandom-67 AC 77 ms 256 KB
05-AllRandom-68 AC 85 ms 384 KB
05-AllRandom-69 AC 85 ms 256 KB