oj.uz

Submission #77681

# Submission time Handle Problem Language Result Execution time Memory
77681 2018-09-29T18:14:25 Z updown1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 660 ms 31900 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, K)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
const int MAXN=1000000, INF=1000000000000000000, MOD=1000000007;;
///500,000,000
int T, N, mul= 41, hsh1[MAXN], inv[MAXN], p[MAXN];
string a;

int see(int st, int en) {
    if (st == 0) return hsh1[en];
    return (((hsh1[en]-hsh1[st-1]+MOD)%MOD)*inv[st])%MOD;
}
int mI(int x, int y) {
    if (y == 0) return 1;
    int p = mI(x, y/2) % MOD;
    p = (p * p) % MOD;

    return (y%2 == 0)? p : (x * p) % MOD;
}


main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    p[0] = 1; For (i, 1, MAXN) p[i] = (p[i-1]*mul)%MOD;
    For (i, 0, MAXN) inv[i] = mI(p[i], MOD-2);
    For (t, 0, T) {
        cin >> a; N = a.length();
        hsh1[0]=a[0]-'a'+1; For (i, 1, N) hsh1[i] = (hsh1[i-1]+ (a[i]-'a'+1)*p[i])%MOD;
        int out = 0;
        int st = 0;
        ffi {
            if (see(st, i) == see(N-i-1, N-st-1)) {
                //w<< st s i<<e;
                out++;
                st = i+1;
            }

        }
        w<<out<<e;
    }
}

Compilation message

palindromic.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 16092 KB Output is correct
2 Correct 471 ms 16092 KB Output is correct
3 Correct 481 ms 16092 KB Output is correct
4 Correct 477 ms 16220 KB Output is correct
5 Correct 468 ms 16220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 16092 KB Output is correct
2 Correct 471 ms 16092 KB Output is correct
3 Correct 481 ms 16092 KB Output is correct
4 Correct 477 ms 16220 KB Output is correct
5 Correct 468 ms 16220 KB Output is correct
6 Correct 503 ms 16388 KB Output is correct
7 Correct 472 ms 16388 KB Output is correct
8 Correct 488 ms 16388 KB Output is correct
9 Correct 475 ms 16388 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 16092 KB Output is correct
2 Correct 471 ms 16092 KB Output is correct
3 Correct 481 ms 16092 KB Output is correct
4 Correct 477 ms 16220 KB Output is correct
5 Correct 468 ms 16220 KB Output is correct
6 Correct 503 ms 16388 KB Output is correct
7 Correct 472 ms 16388 KB Output is correct
8 Correct 488 ms 16388 KB Output is correct
9 Correct 475 ms 16388 KB Output is correct
10 Correct 467 ms 16416 KB Output is correct
11 Correct 481 ms 16484 KB Output is correct
12 Correct 474 ms 16668 KB Output is correct
13 Correct 479 ms 16892 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 16092 KB Output is correct
2 Correct 471 ms 16092 KB Output is correct
3 Correct 481 ms 16092 KB Output is correct
4 Correct 477 ms 16220 KB Output is correct
5 Correct 468 ms 16220 KB Output is correct
6 Correct 503 ms 16388 KB Output is correct
7 Correct 472 ms 16388 KB Output is correct
8 Correct 488 ms 16388 KB Output is correct
9 Correct 475 ms 16388 KB Output is correct
10 Correct 467 ms 16416 KB Output is correct
11 Correct 481 ms 16484 KB Output is correct
12 Correct 474 ms 16668 KB Output is correct
13 Correct 479 ms 16892 KB Output is correct
14 Correct 646 ms 30696 KB Output is correct
15 Correct 575 ms 31888 KB Output is correct
16 Correct 660 ms 31900 KB Output is correct
17 Correct 579 ms 31900 KB Output is correct