oj.uz

Submission #279707

# Submission time Handle Problem Language Result Execution time Memory
279707 2020-08-22T10:01:42 Z BeanZ Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 15;
const int base = 311;
const int mod = 1e9 + 7;
ll h[1000006], p[1000006];
ll get(ll i, ll j){
        return (h[j] - p[j - i + 1] * h[i - 1] + (ll)mod * mod) % mod;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
        ll t;
        cin >> t;
        while (t--){
                string s;
                cin >> s;
                ll n = s.length();
                s = " " + s;
                p[0] = 1;
                for (int i = 1; i <= n; i++){
                        p[i] = p[i - 1] * base % mod;
                }
                for (int i = 1; i <= n; i++){
                        h[i] = (h[i - 1] * base + (s[i] - 'a') + 1) % mod;
                }
                ll lb = 1, rb = 1, le = n, re = n;
                ll ans = 0;
                while (true){
                        if (get(lb, rb) == get(le, re)){
                                lb = rb + 1;
                                re = le - 1;
                                ans += 2;
                                rb++;
                                le--;
                                if (rb > le){
                                        cout << ans << endl;
                                        break;
                                }
                                if (rb == le){
                                        cout << ans + 1 << endl;
                                        break;
                                }
                        } else {
                                rb++;
                                le--;
                                if (rb >= le){
                                        cout << ans + 1 << endl;
                                        break;
                                }
                        }
                }
        }
}
/*
*/

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   18 |                 freopen("VietCT.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:19:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   19 |                 freopen("VietCT.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -