#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll P1 = 41;
const ll P2 = 1000000007;
int T;
string str;
long long str1;
vector<ll> vt;
ll pw(ll x, ll y){
if(y==0) return 1;
if(y==1) return x;
ll m = pw(x, y/2);
if(y%2){
return (((m*m)%P2) * x) % P2;
}else{
return (m*m) % P2;
}
}
bool fnd(ll x){
int s = 0, e = vt.size()-1, m;
while(s<e){
m = (s+e)/2;
if(vt[m]<x) s = m+1;
else e = m;
}
return (vt[s]==x);
}
int calc(){
int x, y;
x = 0; y = str.size()-1;
int ans = 0;
while(1){
if(x>y) return ans;
if(x==y) return ans+1;
ll num = 0;
int l = 1;
while(1){
if(x+l-1 > y-l+1){
return ans+1;
}
num = ((num * P1) + (ll)(str[x+l-1] - 'a' + 1)) % P2;
if(fnd((str1 + num * pw(P1, x))%P2)){
str1 = (str1 + num * pw(P1, x))%P2;
ans += 2;
x = x+l; y = y-l;
break;
}
l++;
}
}
}
int main(){
cin>>T;
while(T--){
cin>>str;
str1 = 0;
ll num = 0;
ll m = 1;
while(!vt.empty()) vt.pop_back();
for(int i=str.size()-1; i>=0; i--){
num = (num + (ll)(str[i]-'a'+1) * m) % P2;
m = (m * P1) % P2;
vt.pb(num);
}
sort(vt.begin(), vt.end());
printf("%d\n", calc());
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
20 ms |
768 KB |
Output is correct |
11 |
Correct |
11 ms |
512 KB |
Output is correct |
12 |
Correct |
21 ms |
512 KB |
Output is correct |
13 |
Correct |
20 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
20 ms |
768 KB |
Output is correct |
11 |
Correct |
11 ms |
512 KB |
Output is correct |
12 |
Correct |
21 ms |
512 KB |
Output is correct |
13 |
Correct |
20 ms |
512 KB |
Output is correct |
14 |
Incorrect |
4359 ms |
10580 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |