oj.uz

답안 #1083369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083369 2024-09-03T03:30:18 Z Requiem Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 356 ms 92400 KB 
#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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 472 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 472 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 1496 KB Output is correct
11 Correct 3 ms 1020 KB Output is correct
12 Correct 3 ms 1496 KB Output is correct
13 Correct 4 ms 1324 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 472 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 1496 KB Output is correct
11 Correct 3 ms 1020 KB Output is correct
12 Correct 3 ms 1496 KB Output is correct
13 Correct 4 ms 1324 KB Output is correct
14 Correct 356 ms 92400 KB Output is correct
15 Correct 171 ms 64740 KB Output is correct
16 Correct 276 ms 92276 KB Output is correct
17 Correct 185 ms 47244 KB Output is correct