oj.uz

Submission #319713

# Submission time Handle Problem Language Result Execution time Memory
319713 2020-11-06T08:55:29 Z erfanmir Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 290 ms 50264 KB 
// In the name of god

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 1e6 + 10;
const int MAXLG = 18;
const int MOD[2] = {1000 * 1000 * 1000 + 7, 998244353};
const ll INF = 8e18;
char ch[MAXN];
int n;
ll hsh[2][MAXN], tav[2][MAXN], a[MAXN];
ll ans;

void preprocess(){
    tav[0][0] = 1;
    tav[1][0] = 1;
    for(int i = 1; i < MAXN; i++){
        tav[0][i] = 26 * tav[0][i - 1] % MOD[0];
        tav[1][i] = 26 * tav[1][i - 1] % MOD[1];
    }
}

ll get(int l, int r, int ind){
    ll res = hsh[ind][r];
    ll kam = (hsh[ind][l - 1] * tav[ind][r - l + 1]) % MOD[ind];
    res -= kam;
    res += MOD[ind];
    res %= MOD[ind];
    return res;
}

int main()
{
    preprocess();
    int t;
    scanf("%d", &t);
    while(t--){
        ans = 0;
        memset(hsh, 0, sizeof hsh);
        memset(a, 0, sizeof a);
        memset(ch, 0, sizeof ch);
        scanf("%s", ch);
        n = strlen(ch);
        for(int i = 1; i <= n; i++){
            a[i] = ch[i - 1] - 'a';
        }
        for(int i = 1; i <= n; i++){
            hsh[0][i] = 26 * hsh[0][i - 1] + a[i];
            hsh[1][i] = 26 * hsh[1][i - 1] + a[i];
            hsh[0][i] %= MOD[0];
            hsh[1][i] %= MOD[1];
        }
        int l = 1, r = n;
        for(int i = 1; l + i - 1 < r - i + 1; i++){
            ll x1, x2, y1, y2;
            x1 = get(l, l + i - 1, 0);
            x2 = get(l, l + i - 1, 1);
            y1 = get(r - i + 1, r, 0);
            y2 = get(r - i + 1, r, 1);
            if(x1 == y1 && x2 == y2){
                ans += 2;
                l = l + i;
                r = r - i;
                i = 0;
            }
        }
        if(l <= r){
            ans++;
        }
        printf("%lld\n", ans);
    }
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 40652 KB Output is correct
2 Correct 57 ms 40488 KB Output is correct
3 Correct 46 ms 40472 KB Output is correct
4 Correct 59 ms 40420 KB Output is correct
5 Correct 56 ms 40444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 40652 KB Output is correct
2 Correct 57 ms 40488 KB Output is correct
3 Correct 46 ms 40472 KB Output is correct
4 Correct 59 ms 40420 KB Output is correct
5 Correct 56 ms 40444 KB Output is correct
6 Correct 59 ms 40512 KB Output is correct
7 Correct 45 ms 40428 KB Output is correct
8 Correct 60 ms 40548 KB Output is correct
9 Correct 58 ms 40420 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 40652 KB Output is correct
2 Correct 57 ms 40488 KB Output is correct
3 Correct 46 ms 40472 KB Output is correct
4 Correct 59 ms 40420 KB Output is correct
5 Correct 56 ms 40444 KB Output is correct
6 Correct 59 ms 40512 KB Output is correct
7 Correct 45 ms 40428 KB Output is correct
8 Correct 60 ms 40548 KB Output is correct
9 Correct 58 ms 40420 KB Output is correct
10 Correct 58 ms 40548 KB Output is correct
11 Correct 45 ms 40444 KB Output is correct
12 Correct 59 ms 40556 KB Output is correct
13 Correct 59 ms 40676 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 40652 KB Output is correct
2 Correct 57 ms 40488 KB Output is correct
3 Correct 46 ms 40472 KB Output is correct
4 Correct 59 ms 40420 KB Output is correct
5 Correct 56 ms 40444 KB Output is correct
6 Correct 59 ms 40512 KB Output is correct
7 Correct 45 ms 40428 KB Output is correct
8 Correct 60 ms 40548 KB Output is correct
9 Correct 58 ms 40420 KB Output is correct
10 Correct 58 ms 40548 KB Output is correct
11 Correct 45 ms 40444 KB Output is correct
12 Correct 59 ms 40556 KB Output is correct
13 Correct 59 ms 40676 KB Output is correct
14 Correct 290 ms 50264 KB Output is correct
15 Correct 165 ms 45616 KB Output is correct
16 Correct 272 ms 49636 KB Output is correct
17 Correct 177 ms 45540 KB Output is correct