Submission #1083369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083369		Requiem	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	356 ms	92400 KiB

palindromic

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define TASKNAME "ppar"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MASK(i) (1LL << i)
#define ii pair<int, int>
#define BIT(x, i) (((x) >> (i))&1)
#define pb push_back
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
using namespace std;

string str;
int n;
template<typename T> bool maximize(T &a, T b){  if (a < b) {a = b; return true; } return false; }
template<typename T> bool minimize(T &a, T b){  if (a > b) {a = b; return true; } return false; }

const int MAXN = 1e6 + 9;
namespace subtask1{
    bool check(){
        return n <= 300;
    }

    int dp[303][303];
    int lps[303][303];

    /**
    sub này ta có thể qhđ để giải.
    **/
    void solve(){
        FORD(i, n, 1){
             FORD(j, n, 1){
                  dp[i][j] = 0;
                  lps[i][j] = 0;
                  if (str[i] == str[j]) lps[i][j] = 1 + lps[i + 1][j + 1];
             }
        }
        FOR(len, 1, n){
            FOR(i, 1, n - len + 1){
                int j = i + len - 1;
                dp[i][j] = 1;
                FOR(k, i, j - 1){
                    int len1 = k - i + 1;
                    int len2 = len1;

                    int t = j - len2 + 1;
                    if (lps[i][t] >= len1 and k < t) maximize(dp[i][j], dp[k + 1][t - 1] + 2);
                }
            }
        }
        printf("%lld\n", dp[1][n]);
    }
}

namespace subtask2{
    bool check(){
        return n <= 10000;
    }

    vector<int> position[27];
    int KMP[MAXN];
    char temp[MAXN];

    int build(int l, int r){
        KMP[1] = 0;
        FOR(i, l, r){
            KMP[i - l + 1] = 0;
            temp[i - l + 1] = str[i];
//            printf("%c", temp[i - l + 1]);
        }
        int len = r - l + 1;
//        printf("\n");
        FOR(i, 2 , len){
            int j = KMP[i - 1];
            while(j > 0 and temp[j + 1] != temp[i]){
                j = KMP[j];
            }
            if (temp[j + 1] == temp[i]) KMP[i] = j + 1;
//            printf("%lld ", KMP[i]);
        }
//        printf("\n");
        int mn = KMP[len];
        if (mn == 0) return len;
        while(mn > 0){
            if (KMP[mn] == 0) return mn;
            mn = KMP[mn];
        }
    }

    void solve(){
         int l = 1, r = n;
         int ans = 0;
         while(l <= r){
             int len = build(l, r);
//             printf("%lld %lld %lld %lld\n", len, ans, l, r);
             if (len == r - l + 1){
                 ans++;
             }
             else ans+=2;
             l = l + len;
             r = r - len;
         }
         printf("%lld\n", ans);

    }
}

namespace subtask3{
    bool check(){
        return true;
    }

    const ii P = ii(113, 97);
    const ii MOD = ii(1e9 + 7, 998244353);
    int cong(int a, int b, int mod){
        return (a + b) % mod;
    }

    int tru(int a, int b, int mod){
        return ((a - b) % mod + mod) % mod;
    }
    int nhan(int a, int b, int mod){
        return (1LL * a * b) % mod;
    }

    ii operator + (ii a, ii b){
        return ii(cong(a.fi, b.fi, MOD.fi), cong(a.se, b.se, MOD.se));
    }

    ii operator - (ii a, ii b){
        return ii(tru(a.fi, b.fi, MOD.fi), tru(a.se, b.se, MOD.se));
    }

    ii operator * (ii a, ii b){
        return ii(nhan(a.fi, b.fi, MOD.fi), nhan(a.se, b.se, MOD.se));
    }

    ii hashCode[MAXN], PW[MAXN];

    ii getHash(int l, int r){
        return hashCode[r] - hashCode[l - 1] * PW[r - l + 1];
    }

    bool operator == (ii a, ii b){
        return (a.fi == b.fi and a.se == b.se);
    }
    vector<int> position[27];
    void solve(){
        PW[0] = {1, 1};
        FOR(i, 1, n){
            PW[i] = PW[i - 1] * P;
        }
        FOR(i, 1, n){
            hashCode[i] = hashCode[i - 1] * P + ii(str[i] - 'a' + 1, str[i] - 'a' + 1);
            position[str[i] - 'a'].pb(i);
        }
//        ii g1 = getHash(1, 2);
//        ii g2 = getHash(5, 6);
//        printf("%lld %lld\n", g1.fi, g1.se);
//        printf("%lld %lld\n", g2.fi, g2.se);

        int l = 1, r = n, ans = 0;
        while(l <= r){
            int mn = r - l + 1;
//            printf("??");
            FORD(i, (int) position[(str[l] - 'a')].size() - 1, 0){
                int v = position[(str[l] - 'a')][i];
//                printf("%lld %lld\n", l, v);
                if (v < l) {
                    mn = r - l + 1; break;
                }
                ii g1 = getHash(l, l + r - v);
                ii g2 = getHash(v, r);
//                printf("%lld %lld\n", g1.fi, g1.se);
//                printf("%lld %lld\n", g2.fi, g2.se);
                if (getHash(l, l + r - v) == getHash(v, r)) {
                    minimize(mn, r - v + 1);
//                    printf("%lld %lld\n", l, v);
                    break;
                }
            }


            if (mn == r - l + 1) ans++;
            else ans += 2;
            l = l + mn;
            r = r - mn;
            FOR(i, 0, 25){
                while(position[i].size() > 0 and position[i].back() > r) position[i].pop_back();
            }

        }
        printf("%lld\n", ans);
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    int t;
    cin >> t;
    while(t--){
        cin >> str;
        n = str.length();
        str = '#' + str;
//        if (subtask1::check()) subtask1::solve();
//        if (subtask2::check()) subtask2::solve();
        if (subtask3::check()) subtask3::solve();
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'void subtask3::solve()':
palindromic.cpp:175:20: warning: variable 'g1' set but not used [-Wunused-but-set-variable]
  175 |                 ii g1 = getHash(l, l + r - v);
      |                    ^~
palindromic.cpp:176:20: warning: variable 'g2' set but not used [-Wunused-but-set-variable]
  176 |                 ii g2 = getHash(v, r);
      |                    ^~
palindromic.cpp: At global scope:
palindromic.cpp:199:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  199 | main(){
      | ^~~~
palindromic.cpp: In function 'long long int subtask2::build(long long int, long long int)':
palindromic.cpp:91:5: warning: control reaches end of non-void function [-Wreturn-type]
   91 |     }
      |     ^
palindromic.cpp: In function 'int main()':
palindromic.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40