oj.uz

Submission #1095074

# Submission time Handle Problem Language Result Execution time Memory
1095074 2024-10-01T08:25:43 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 140 ms 50260 KB 
//------------------------------------\
//   ------------------------------   \
//  |    created by Pham Phuongg   |  \
//  |       phamvuphuong2008       |  \
//  |     THPT CHUYEN HA TINH      |  \
//  |      HA TINH, VIET NAM       |  \
//  |    Bé Phương from TK4-CHT    |  \
//   ------------------------------   \
//------------------------------------\

#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
//#define ii pair<int ,int >
#define endl '\n'
#define iii pair<int,ii>
#define pb push_back
#define task "main"
#define base 145443351LL
using namespace std;
const int maxn = 1e6+5;
const int lim = 1e6;
long long mod = 1e9+7;
long long pot[maxn], Hash[maxn], n;
string s;

 bool compare(int i, int j, int ii, int jj) {
    long long dx = (i > 0 ? Hash[i - 1] : 0);
    long long A = (mod + Hash[j] - dx) % mod;
    
    long long dx2 = (ii > 0 ? Hash[ii - 1] : 0);
    long long A2 = (mod + Hash[jj] - dx2) % mod;
    
    return (((A * pot[ii]) % mod) == ((A2 * pot[i]) % mod));
}

int dq(int ini) {
    int fim = s.size() - 1 - ini;

    if (ini == fim) return 1;

    if (ini > fim) return 0;

    int best = 1;

    for (int p = ini; p <= (ini + fim) / 2; p++) {
        if (compare(ini, p, fim - p + ini, fim)) {
            best = max(best, 2 + dq(p + 1));
            break;
        }
    }

    return best;
}

void solve() {
    cin >> s;
    n = s.length();
    
    Hash[0] = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0) Hash[i] = Hash[i - 1];
        Hash[i] = (Hash[i] + s[i] * pot[i]) % mod;
    }
    cout << dq(0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    if (fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    
    pot[0] = 1;
    for (int i = 1; i <= lim; i++) pot[i] = (pot[i - 1] * base) % mod;

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
}

Compilation message

palindromic.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\
      | ^
palindromic.cpp: In function 'int main()':
palindromic.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8252 KB Output is correct
2 Correct 9 ms 8264 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 8 ms 8280 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8252 KB Output is correct
2 Correct 9 ms 8264 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 8 ms 8280 KB Output is correct
6 Correct 8 ms 8280 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 9 ms 8284 KB Output is correct
10 Correct 9 ms 8540 KB Output is correct
11 Correct 9 ms 8540 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 8 ms 8496 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8252 KB Output is correct
2 Correct 9 ms 8264 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8284 KB Output is correct
5 Correct 8 ms 8280 KB Output is correct
6 Correct 8 ms 8280 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 9 ms 8284 KB Output is correct
10 Correct 9 ms 8540 KB Output is correct
11 Correct 9 ms 8540 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 8 ms 8496 KB Output is correct
14 Correct 140 ms 50260 KB Output is correct
15 Correct 73 ms 37100 KB Output is correct
16 Correct 101 ms 26352 KB Output is correct
17 Correct 65 ms 24284 KB Output is correct