oj.uz

Submission #320599

# Submission time Handle Problem Language Result Execution time Memory
320599 2020-11-09T08:26:59 Z AriaH Palindromic Partitions (CEOI17_palindromic) C++11
0 / 100
 1 ms 364 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 1e5 + 10;
const int LOG = 24;

string s;

ll pw[2][N], Hsh[2][N], mod[2], base = 737, n;

pll baze(ll l, ll r)
{
    return Mp((Hsh[0][r] - ((Hsh[0][l - 1] * pw[0][r - l + 1]) % mod[0]) + mod[0]) % mod[0], (Hsh[1][r] - (Hsh[1][l - 1] * pw[1][r - l + 1] % mod[1]) + mod[1]) % mod[1]);
}

int is_eq(int l, int r, int sz)
{
    if(baze(l, l + sz - 1) == baze(r - sz + 1, r)) return 1;
    return 0;
}

void B()
{
    pw[0][0] = pw[1][0] = 1;
    for(int i = 1; i <= n; i ++)
    {
	for(int j = 0; j < 2; j ++)
	{
	    pw[j][i] = (pw[j][i - 1] * base) % mod[j];
	    Hsh[j][i] = (Hsh[j][i - 1] * base + s[i] - 'a' + 1) % mod[j];
	}
    }
}

inline void solve()
{
    cin >> s;
    n = (int)s.size();
    s = "." + s;
    B();
    int l = 1, r = n, ans = 1, sz = 1;
    while(l <= r)
    {
	while(l + sz < n && r - sz + 1 > 0 && !is_eq(l, r, sz)) sz ++;
	if(l + sz - 1 >= r - sz + 1) break;
	if(l + sz == r - sz + 1) { ans ++; break; }
	ans += 2;
	l += sz;
	r -= sz;
	sz = 1;
    }
    cout << ans << endl;
}

int main()
{
    mod[0] = 1e9 + 7;
    mod[1] = 1e9 + 9;
    int q;
    cin >> q;
    while(q--)
    {
	solve();
    }
    return 0;
}
/*!
        stay away from negative people they have a problem for every solution !
*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -