oj.uz

Submission #162251

# Submission time Handle Problem Language Result Execution time Memory
162251 2019-11-07T10:11:26 Z karma Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 18 ms 10308 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(2e5) + 7;
const int mod = int(1e9) + 9;
const ll sqrMod = 1ll * mod * mod;
const ll Base = 33;
typedef pair<int, int> pii;

ll Hash[N], p[N];
string s;
int n;

int GetHash(int l, int r) {return (Hash[r] - Hash[l - 1] * p[r - l + 1] + sqrMod) % mod;}

void Solve() {
    cin >> s; s = ' ' + s;
    n = int(s.size()) - 1;
    for(int i = 1; i <= n; ++i) Hash[i] = (Hash[i - 1] * Base + s[i] - 'a') % mod;
    int i = 1, j = n, len = 1, res = 0;
    while(i <= j) {
        if(GetHash(i, i + len - 1) == GetHash(j - len + 1, j)) {
           if(i + len - 1 < j - len + 1) res += 2;
           else ++res;
           //cout << i << ' ' << j << ' ' << len << '\n';
           i = i + len; j = j - len; len = 1;
        } else ++len;
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    p[0] = 1;
    for(int i = 1; i < N; ++i) p[i] = p[i - 1] * Base % mod;
    int nTest; cin >> nTest;
    while(nTest --) Solve();
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 4 ms 1912 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct
4 Correct 4 ms 1912 KB Output is correct
5 Correct 5 ms 1912 KB Output is correct
6 Correct 4 ms 1912 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 5 ms 1912 KB Output is correct
10 Correct 6 ms 2168 KB Output is correct
11 Correct 6 ms 2040 KB Output is correct
12 Correct 6 ms 2168 KB Output is correct
13 Correct 6 ms 2040 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 4 ms 1912 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct
4 Correct 4 ms 1912 KB Output is correct
5 Correct 5 ms 1912 KB Output is correct
6 Correct 4 ms 1912 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 5 ms 1912 KB Output is correct
10 Correct 6 ms 2168 KB Output is correct
11 Correct 6 ms 2040 KB Output is correct
12 Correct 6 ms 2168 KB Output is correct
13 Correct 6 ms 2040 KB Output is correct
14 Runtime error 18 ms 10308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -