oj.uz

Submission #858626

# Submission time Handle Problem Language Result Execution time Memory
858626 2023-10-09T03:04:32 Z ngonhatmin Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 137 ms 42268 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
#define mp make_pair
#define TWO(x) (1<<(x))
#define BIT(s,i) (((s)&TWO(i))>0)
#define ON(s,i) (s |= TWO(i))
#define OFF(s,i) (s &= ~TWO(i))
#define FLIP(s,i) (s ^= TWO(i))
#define vvec vector<vector<int>>

struct ngocon{
    int x,y,z;
};

typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> pipi;

const int h4[4] = {1,0,-1,0}; /// 4 huong
const int c4[4] = {0,1,0,-1}; /// 4 huong
const int h8[8] = {-1,-1,-1,0,1,1,1,0}; /// 8 huong
const int c8[8] = {-1,0,1,1,1,0,-1,-1}; /// 8 huong
const int cv1[8] = {1,2,2,1,-1,-2,-2,-1}; /// 8 huong quan ma
const int cv2[8] = {-2,-1,1,2,2,1,-1,-2}; /// 8 huong quan ma
const int mod1 = 1e9 + 7; /// chia du
const int mod2 = 1e6 + 3;
const int base = 26; /// ma hoa
const int oo = 1e16;
const int N = 1e6 + 2;

int n;
int Pow1[N],Pow2[N],Hash1[N],Hash2[N];
string s;

int get_hash1(int i, int j){
    return (Hash1[j] - (Hash1[i-1]*Pow1[j-i+1]) % mod1 + mod1) % mod1;
}

int get_hash2(int i, int j){
    return (Hash2[j] - (Hash2[i-1]*Pow2[j-i+1]) % mod2 + mod2) % mod2;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);

    Pow1[0] = Pow2[0] = 1;
    FOR(i,1,1000000){
        Pow1[i] = (Pow1[i-1] * base) % mod1;
        Pow2[i] = (Pow2[i-1] * base) % mod2;
    }

    int t; cin >> t;
    while(t--){
        cin >> s;
        n = s.size(); s = ' ' + s;

        //cout << s[1] << ' ' << s[n] << '\n';

        Hash1[0] = Hash2[0] = 0;
        FOR(i,1,n){
            Hash1[i] = (Hash1[i-1] * base + s[i] - 'a') % mod1;
            Hash2[i] = (Hash2[i-1] * base + s[i] - 'a') % mod2;
        }

        int bg1 = 1, ed1 = 1, bg2 = n, ed2 = n, result = 0;
        while(ed1 < bg2){
            if (get_hash1(bg1,ed1) == get_hash1(bg2,ed2) &&
                get_hash2(bg1,ed1) == get_hash2(bg2,ed2)){
                result += 2;
                //cout << bg1 << ' ' << ed1 << ' ' << bg2 << ' ' << ed2 << '\n';
                if (ed1 + 1 == bg2) break;
                bg1 = ed1 = ed1 + 1;
                ed2 = bg2 = bg2 - 1;
            }
            else{
                ed1++;
                bg2--;
            }
        }
        if (ed1 + 1 == bg2) cout << result << '\n';
        else cout << result + 1 << '\n';
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19184 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19544 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 7 ms 19292 KB Output is correct
9 Correct 8 ms 19396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19184 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19544 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 7 ms 19292 KB Output is correct
9 Correct 8 ms 19396 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 8 ms 19292 KB Output is correct
12 Correct 9 ms 19292 KB Output is correct
13 Correct 9 ms 19292 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19184 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19544 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 7 ms 19292 KB Output is correct
9 Correct 8 ms 19396 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 8 ms 19292 KB Output is correct
12 Correct 9 ms 19292 KB Output is correct
13 Correct 9 ms 19292 KB Output is correct
14 Correct 137 ms 41704 KB Output is correct
15 Correct 74 ms 37888 KB Output is correct
16 Correct 121 ms 42268 KB Output is correct
17 Correct 77 ms 32984 KB Output is correct