Submission #1303375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303375		mr_fin	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	399 ms	42484 KiB

palindromic

#include <bits/stdc++.h>

#define nl      1000007
#define bg_NUM  1000000009


#define fi first
#define se second
#define sz() size()


#define ll long long
#define ps push_back
#define pii pair<int,int>
//#define int long long


using namespace std;


mt19937_64 rd(time(0));
long long Random( long long l , long long r ) { return l + rd() % (r-l+1) ; }


int T;
vector<string> S;

int n;
ll hs[5][nl], pw[5][nl];
ll base[5] = { 113, 317, 77, 101 };
ll mod[5] = { 1092009103, 1312323217, 727313771, 919191309 };


pair<pair<ll,ll>,pair<ll,ll>> get( int l, int r ) {

    return {

        {(((hs[0][r] - hs[0][l-1] + mod[0]*mod[0]) % mod[0]) * pw[0][n-r]) % mod[0],
        (((hs[1][r] - hs[1][l-1] + mod[1]*mod[1]) % mod[1]) * pw[1][n-r]) % mod[1]},

        {(((hs[2][r] - hs[2][l-1] + mod[2]*mod[2]) % mod[2]) * pw[2][n-r]) % mod[2],
        (((hs[3][r] - hs[3][l-1] + mod[3]*mod[3]) % mod[3]) * pw[3][n-r]) % mod[3]}
    };
}


//pair<ll,ll> get( int l, int r ) {
//
//    return {
//
//        (((hs[0][r] - hs[0][l-1] + mod[0]*mod[0]) % mod[0]) * pw[0][n-r]) % mod[0],
//        (((hs[1][r] - hs[1][l-1] + mod[1]*mod[1]) % mod[1]) * pw[1][n-r]) % mod[1]
//    };
//}



void Solve( string &s ) {

    n = s.sz();
    s = " " + s;
    for( int tp = 0 ; tp < 2 ; tp ++ ) {

        hs[tp][0] = 0;
        for( int i = 1 ; i <= n ; i ++ )
            hs[tp][i] = (hs[tp][i-1] + 1ll*(s[i]-'a'+1)*pw[tp][i-1]) % mod[tp];
    }


    int cnt = 0, i = 1, r = n;
    while(1) {

        int res = -1;
        for( int len = 1 ; len <= (r-i+1)/2 ; len ++ ) {

            if(get(i,i+len-1) == get(r-len+1,r)) {

                res = len;
                cnt += 2;
                break;
            }
        }

        if(res < 0) {

            if(i <= r)cnt ++;
            break;
        }

        i += res;
        r -= res;
    }
    cout << cnt << '\n';
}

void Process() {

    for( int i = 1 ; i <= T ; i ++ )
        Solve(S[i]);
}


void Test() {

    ofstream out("SIXCUP.inp");

    int Ntest = 20;
    out << Ntest << '\n';

    while(Ntest --) {

        int sz = Random(5000,70000);
        while(sz--) out << char(Random('a','z'));
        out <<'\n';
    }
}

 int main() {

    #define Beta "SIXCUP"
    if( fopen( Beta ".INP", "r" ) ){

        freopen( Beta ".INP", "r", stdin )  ;
        freopen( Beta ".OUT", "w", stdout ) ;
    }

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //Test();

    cin >> T;
    S.resize(T+1);

    for( int i = 1 ; i <= T ; i ++ )
        cin >> S[i];


    for( int tp = 0 ; tp < 2 ; tp ++ ) {

        pw[tp][0] = 1;
        for( int i = 1 ; i <= nl-7 ; i ++ )
            pw[tp][i] = (pw[tp][i-1]*base[tp])%mod[tp];
    }

    Process();
}


/*

NHO XOA COMMENT !!!

4
gspvhcute
anhanh
anhhanh
diduadudi
*/

Compilation message (stderr)

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

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