oj.uz

Submission #147272

# Submission time Handle Problem Language Result Execution time Memory
147272 2019-08-28T16:29:19 Z claudy Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 442 ms 36052 KB 
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

/*
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
Tree<int>tr;
*/

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// 6:35

const int P = 31;
const int mod = 1e9 + 9;

int t,p[1 << 20],inv[1 << 20],pref[1 << 20],suff[1 << 20];

int mypow(int x,int p)
{
	int ans = 1;
	for(int i = 0;(1LL << i) <= p;i++){
		if(p & (1LL << i)){
			ans *= x;
			ans %= mod;
		}
		x *= x;
		x %= mod;
	}
	return ans;
}

int32_t main(){_
	//freopen("input","r",stdin);
	cin >> t;
	p[0] = 1;
	for(int i = 1;i <= 1000000;i++) p[i] = (P * p[i - 1]) % mod;
	for(int i = 0;i <= 1000000;i++) inv[i] = mypow(p[i],mod - 2);
	while(t--){
		string s;
		cin >> s;
		int n = sz(s);
		for(int i = 0;i < n;i++){
			int x = 0;
			if(i > 0) x = pref[i - 1];
			pref[i] = (x + (s[i] - 'a') * p[i]) % mod;
		}
		for(int i = n - 1;i >= 0;i--){
			int x = 0;
			if(i < n - 1) x = suff[i + 1];
			suff[i] = ((x * P) % mod + s[i] - 'a') % mod;
		}
		int l = 0;
		int r = n - 1;
		int ans = 0;
		while(l <= r){
			bool ok = 0;
			for(int i = l;i < r - i + l;i++){
				if(ok) break;
				int a = ((pref[i] - (l ? pref[l - 1] : 0)) * inv[l]) % mod;
				if(a < 0) a += mod;
				int x = r - i + l;
				int b = (suff[x] - suff[r + 1] * p[r + 1 - x]) % mod;
				if(b < 0) b += mod;
				if(a == b){
					ok = 1;
					r = x - 1;
					l = i + 1;
				}
			}
			if(!ok){
				ans++;
				break;
			}
			else ans += 2;
		}
		memset(pref,0,sizeof(pref));
		memset(suff,0,sizeof(suff));
		cout << ans << '\n';
	}
	return 0;
}

Compilation message

palindromic.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 32520 KB Output is correct
2 Correct 201 ms 32376 KB Output is correct
3 Correct 198 ms 32376 KB Output is correct
4 Correct 204 ms 32504 KB Output is correct
5 Correct 202 ms 32340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 32520 KB Output is correct
2 Correct 201 ms 32376 KB Output is correct
3 Correct 198 ms 32376 KB Output is correct
4 Correct 204 ms 32504 KB Output is correct
5 Correct 202 ms 32340 KB Output is correct
6 Correct 201 ms 32376 KB Output is correct
7 Correct 197 ms 32424 KB Output is correct
8 Correct 210 ms 32376 KB Output is correct
9 Correct 201 ms 32456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 32520 KB Output is correct
2 Correct 201 ms 32376 KB Output is correct
3 Correct 198 ms 32376 KB Output is correct
4 Correct 204 ms 32504 KB Output is correct
5 Correct 202 ms 32340 KB Output is correct
6 Correct 201 ms 32376 KB Output is correct
7 Correct 197 ms 32424 KB Output is correct
8 Correct 210 ms 32376 KB Output is correct
9 Correct 201 ms 32456 KB Output is correct
10 Correct 205 ms 32592 KB Output is correct
11 Correct 205 ms 32392 KB Output is correct
12 Correct 202 ms 32504 KB Output is correct
13 Correct 205 ms 32504 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 32520 KB Output is correct
2 Correct 201 ms 32376 KB Output is correct
3 Correct 198 ms 32376 KB Output is correct
4 Correct 204 ms 32504 KB Output is correct
5 Correct 202 ms 32340 KB Output is correct
6 Correct 201 ms 32376 KB Output is correct
7 Correct 197 ms 32424 KB Output is correct
8 Correct 210 ms 32376 KB Output is correct
9 Correct 201 ms 32456 KB Output is correct
10 Correct 205 ms 32592 KB Output is correct
11 Correct 205 ms 32392 KB Output is correct
12 Correct 202 ms 32504 KB Output is correct
13 Correct 205 ms 32504 KB Output is correct
14 Correct 442 ms 35504 KB Output is correct
15 Correct 326 ms 35668 KB Output is correct
16 Correct 426 ms 36052 KB Output is correct
17 Correct 344 ms 34752 KB Output is correct