oj.uz

Submission #409319

# Submission time Handle Problem Language Result Execution time Memory
409319 2021-05-20T14:56:45 Z Hazem Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 347 ms 18432 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 1e6+10;
const int M = 101;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

string s;
int chash[N];
int powers[N];

int add(LL a,LL b){
    return (a+b)%MOD;
}

int mult(LL a,LL b){
    return (a*b)%MOD;
}


bool check(int l1,int r1,int l2,int r2){

    LL h1 = ((chash[r2]-chash[l2-1])%MOD+MOD)%MOD;
    LL h2 = ((chash[r1]-(l1?chash[l1-1]:0))%MOD+MOD)%MOD;
    h2 = mult(h2,powers[l2-l1]);

    return h1==h2;
}

int solve(int l,int r){

    if(l>r)
        return 0;

    for(int i=l;i<(l+r+1)/2;i++)
        if(check(l,i,r-(i-l),r))
            return 2+solve(i+1,r-(i-l)-1);

    return 1;
}

int main(){

    //freopen("out.txt","w",stdout);
    powers[0] = 1;
    for(int i=1;i<=1e6;i++)
        powers[i] = mult(powers[i-1],31);

    int t;
    scanf("%d",&t);

    while(t--){

        cin>>s;
        int n  = s.size();
    
        for(int i=0;i<n;i++)
            chash[i] = add(i?chash[i-1]:0,mult(s[i]-'a'+1,powers[i]));

        printf("%d\n",solve(0,n-1));     
    }
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4176 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4176 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 8 ms 4172 KB Output is correct
7 Correct 8 ms 4172 KB Output is correct
8 Correct 9 ms 4116 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4176 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 8 ms 4172 KB Output is correct
7 Correct 8 ms 4172 KB Output is correct
8 Correct 9 ms 4116 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 11 ms 4232 KB Output is correct
11 Correct 10 ms 4172 KB Output is correct
12 Correct 11 ms 4184 KB Output is correct
13 Correct 11 ms 4172 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4176 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 8 ms 4172 KB Output is correct
7 Correct 8 ms 4172 KB Output is correct
8 Correct 9 ms 4116 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 11 ms 4232 KB Output is correct
11 Correct 10 ms 4172 KB Output is correct
12 Correct 11 ms 4184 KB Output is correct
13 Correct 11 ms 4172 KB Output is correct
14 Correct 347 ms 15776 KB Output is correct
15 Correct 183 ms 14288 KB Output is correct
16 Correct 324 ms 18432 KB Output is correct
17 Correct 189 ms 12144 KB Output is correct