oj.uz

Submission #245858

# Submission time Handle Problem Language Result Execution time Memory
245858 2020-07-07T15:42:57 Z Goolakh Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 79 ms 20756 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e6+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

const ll B=619;
ll pw[maxn];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	pw[0]=1; for(int i=1;i<maxn;i++) pw[i]=pw[i-1]*B%mod;
	ll T; cin>>T;
	while(T--){
		string s; cin>>s;
		ll l=0,r=SZ(s)-1,sr=0,ans=0,lh=0,rh=0;
		while(l<r){
			lh=(lh*B%mod+(s[l++]-'a'+1))%mod;
			rh=(pw[sr++]*(s[r--]-'a'+1)%mod+rh)%mod;
			if(lh==rh) ans+=2, lh=rh=sr=0;
		}
		cout<<ans+(lh!=0||l==r)<<endl;
	}
 	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8192 KB Output is correct
2 Correct 13 ms 8192 KB Output is correct
3 Correct 14 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 14 ms 8192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8192 KB Output is correct
2 Correct 13 ms 8192 KB Output is correct
3 Correct 14 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 14 ms 8192 KB Output is correct
6 Correct 13 ms 8192 KB Output is correct
7 Correct 13 ms 8192 KB Output is correct
8 Correct 13 ms 8192 KB Output is correct
9 Correct 13 ms 8192 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8192 KB Output is correct
2 Correct 13 ms 8192 KB Output is correct
3 Correct 14 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 14 ms 8192 KB Output is correct
6 Correct 13 ms 8192 KB Output is correct
7 Correct 13 ms 8192 KB Output is correct
8 Correct 13 ms 8192 KB Output is correct
9 Correct 13 ms 8192 KB Output is correct
10 Correct 15 ms 8320 KB Output is correct
11 Correct 13 ms 8192 KB Output is correct
12 Correct 16 ms 8320 KB Output is correct
13 Correct 14 ms 8320 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8192 KB Output is correct
2 Correct 13 ms 8192 KB Output is correct
3 Correct 14 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 14 ms 8192 KB Output is correct
6 Correct 13 ms 8192 KB Output is correct
7 Correct 13 ms 8192 KB Output is correct
8 Correct 13 ms 8192 KB Output is correct
9 Correct 13 ms 8192 KB Output is correct
10 Correct 15 ms 8320 KB Output is correct
11 Correct 13 ms 8192 KB Output is correct
12 Correct 16 ms 8320 KB Output is correct
13 Correct 14 ms 8320 KB Output is correct
14 Correct 79 ms 20756 KB Output is correct
15 Correct 49 ms 15668 KB Output is correct
16 Correct 76 ms 19704 KB Output is correct
17 Correct 50 ms 14804 KB Output is correct