oj.uz

Submission #1095077

# Submission time Handle Problem Language Result Execution time Memory
1095077 2024-10-01T08:28:12 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 97 ms 19488 KB 
#include<bits/stdc++.h>

#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back//khi dùng pair
#define emb emplace_back//k pair
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+3;
int n,ans,base=31;
string s;
long long f[N],c[N];
int  kc(int i,int j){
    return ((1LL*f[j]-1LL*f[i-1]*c[j-i+1])%mod+mod)%mod;
}
void solve(){
    ans=0;
    cin >> s;
    n=s.size();
    s=" "+s;
    int r=1,l=n;
    for(int i=1;i<=n;++i)f[i]=(f[i-1]*base+s[i]-'a'+1)%mod;
    for(int i=1,j=n;i<j;++i,--j){
        if(kc(r,i)==kc(j,l)){
            // cout <<r<<" "<<i<<" "<<j<<" "<<l<<'\n';
            r=i+1;l=j-1;
            ans+=2;

        }
    }
    if(r<=l)++ans;
    cout << ans;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    c[0]=1;
    for(int i=1;i<=N-5;++i)c[i]=(c[i-1]*base)%mod;
    int t=1;
   cin >> t;
while(t--){
    solve();
    cout<<'\n';
}

}

Compilation message

palindromic.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 7 ms 8276 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 7 ms 8276 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 9 ms 8280 KB Output is correct
11 Correct 8 ms 8284 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 7 ms 8276 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 9 ms 8280 KB Output is correct
11 Correct 8 ms 8284 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct
14 Correct 97 ms 18040 KB Output is correct
15 Correct 60 ms 17940 KB Output is correct
16 Correct 95 ms 19488 KB Output is correct
17 Correct 55 ms 13300 KB Output is correct