제출 #1170602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170602		InvMOD	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	1 ms	320 KiB

palindromic

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

const int MOD = 1e9 + 5277, base = 31;

void solve()
{
    string s; cin >> s;

    s = " " + s; int n = sz(s) - 1;

    // brute
    vector<int> hsh(sz(s)), pw(sz(s), 1);
    for(int i = 1; i < sz(s); i++){
        hsh[i] = hsh[i - 1] * base % MOD + (s[i] - 'a' + 1);
        pw[i] = pw[i - 1] * base % MOD;
    }

    auto get_hash = [&](int l, int r) -> int{
        return (hsh[r] - (hsh[l - 1] * pw[r - l + 1] % MOD) + MOD) % MOD;
    };

    vector<int> dp(sz(s) / 2 + 1, 0);
    for(int i = 1; i <= sz(s) / 2; i++){
        for(int j = 1; j <= i; j++){
            if(get_hash(j, i) == get_hash(n - i + 1, n - j + 1)){
                dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
    }

    int answer = 0;
    for(int i = 1; i <= sz(s) / 2; i++){
        answer = max(answer, dp[i] * 2 + (i != (sz(s)) / 2 ? 1 : -1));
    }

    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

palindromic.cpp: In function 'int main()':
palindromic.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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