oj.uz

Submission #164441

# Submission time Handle Problem Language Result Execution time Memory
164441 2019-11-20T15:20:21 Z kungfulon Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 59 ms 12884 KB 
///Phạm Nguyễn Tuấn Hoàng///
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define repd(i,a,b) for(int i = (a);i >= (b);i--)
#define F first
#define S second
#define PB push_back
#define Task ""
using namespace std;
//template <class T> inline read(T &a){a = 0;char c;bool nega = 0;while(!isdigit(c = getchar()) && c != '-');if(c == '-') nega = 1,c = getchar();a = c - 48;while(isdigit(c = getchar()))a = a * 10 + c - 48;if(nega) a = -a;}
//template <class T> inline writep(T a){if(a > 9) writep(a / 10);putchar(a % 10 + 48);}
//template <class T> inline write(T a){if(a < 0) putchar('-'),a = -a;writep(a);putchar(' ');}
//template <class T> inline writeln(T a){write(a);putchar('\n');}
const int mod = 1000000007,base = 31;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    freopen(Task".inp","r",stdin);
//    freopen(Task".out","w",stdout);

    int T;
    cin >> T;
    while(T--)
    {
        string s;
        cin >> s;
        int n = s.size();
        s = ' ' + s;
        int End = n,Begin = 1,cnt = 0,lastEnd = n + 1;
        long long h1 = 0,h2 = 0,hh = 1;
        while(End > Begin)
        {
            h1 = (h1 * base + s[Begin]) % mod;
            h2 = (s[End] * hh + h2) % mod;
            hh = hh * base % mod;
            if(h1 == h2)
            {
                cnt += 2;
                lastEnd = End;
                h1 = h2 = 0;
                hh = 1;
            }
            End--,Begin++;
        }
        cout << cnt + (lastEnd != Begin) << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 504 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 57 ms 12884 KB Output is correct
15 Correct 34 ms 7796 KB Output is correct
16 Correct 59 ms 12004 KB Output is correct
17 Correct 35 ms 6928 KB Output is correct