oj.uz

Submission #1095076

# Submission time Handle Problem Language Result Execution time Memory
1095076 2024-10-01T08:28:02 Z sasde Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 100 ms 19556 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 7 ms 8280 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8128 KB Output is correct
5 Correct 7 ms 8280 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8280 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8128 KB Output is correct
5 Correct 7 ms 8280 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 8284 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 7 ms 8280 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8128 KB Output is correct
5 Correct 7 ms 8280 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 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 8 ms 8536 KB Output is correct
11 Correct 8 ms 8280 KB Output is correct
12 Correct 9 ms 8396 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 7 ms 8280 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8128 KB Output is correct
5 Correct 7 ms 8280 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 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 8 ms 8536 KB Output is correct
11 Correct 8 ms 8280 KB Output is correct
12 Correct 9 ms 8396 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct
14 Correct 100 ms 18036 KB Output is correct
15 Correct 59 ms 17944 KB Output is correct
16 Correct 91 ms 19556 KB Output is correct
17 Correct 57 ms 13300 KB Output is correct