oj.uz

Submission #310740

# Submission time Handle Problem Language Result Execution time Memory
310740 2020-10-07T19:03:55 Z ly20 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 665 ms 26856 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10, MOD = 1e9 + 7, P = 29;
string s;
int t;
long long hs[MAXN], pot[MAXN];
long long val(int i, int j) {
    long long resp = hs[i] - (hs[j + 1] * pot[j - i + 1]) % MOD;
    resp += MOD;
    resp %= MOD;
    return resp;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        cin >> s;
        int n = s.size();
        pot[0] = 1;
        for(int i = 1; i <= n; i++) {
            pot[i] = pot[i - 1] * P;
            pot[i] %= MOD;
        }
        hs[n] = 0;
        for(int i = n - 1; i >= 0; i--) {
            hs[i] = hs[i + 1] * P + (s[i] - 'a');
            hs[i] %= MOD;
        }
        int ini1 = 0, fim1 = 0, ini2 = n - 1, fim2 = n - 1;
        int resp = 0;
        while(fim1 < fim2) {
            long long vl1 = val(ini1, fim1), vl2 = val(fim2, ini2);
            if(vl1 == vl2) {
                resp += 2;
                ini1 = fim1 + 1; fim1 = ini1;
                ini2 = fim2 - 1; fim2 = ini2;
            }
            else {
                fim1++; fim2--;
            }
        }
        if(ini1 <= ini2) resp++;
        printf("%d\n", resp);
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 6 ms 512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 665 ms 26856 KB Output is correct
15 Correct 357 ms 22272 KB Output is correct
16 Correct 624 ms 26344 KB Output is correct
17 Correct 354 ms 14508 KB Output is correct