oj.uz

Submission #915857

# Submission time Handle Problem Language Result Execution time Memory
915857 2024-01-24T19:24:21 Z AtabayRajabli Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 203 ms 18948 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

// author : a1abay
// (a / b) % c = (a * b ^ (mod - 2)) % c;
 
#define pb          push_back
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define all(v)      v.begin(), v.end()
#define whole(a)    a+1, a+1+n
#define se          second
#define fi          first
#define int         ll
#define print(k)    cerr << "Ans : "; cout << k << endl;
#define ins         insert
#define bpc         __builtin_popcountll
#define skip        continue
#define endll          '\n'
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   (a*b / (__gcd(a, b)))
#define mpr         make_pair
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

typedef long long           ll;
typedef unsigned long long  ull;
typedef long double         ld;
const int sz =              1e6 + 5;
using namespace             std;

void open(string s, string f)
{
    freopen((s + ".txt").c_str(), "r", stdin);
    freopen((f + ".txt").c_str(), "w", stdout);
}

int mod = 1e9 + 7;
int P = 53;

int n, p[sz], pr[sz], sf[sz];

bool check(int l, int lx, int r, int rx)
{
    int a = (pr[l] - pr[lx] + mod) % mod;
    int b = (pr[rx - 1] - pr[r - 1] + mod) % mod;
    return a * p[r - lx - 1] % mod == b;
}

void solve()
{
    string s;
    cin >> s;

    n = s.size();
    
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * P % mod;
        pr[i] = pr[i - 1] + (s[i - 1] - 'a' + 1) * p[i] % mod;
    }

    int l = 1, r = n, lx = 0, rx = n + 1, ans = 0;
    while(l < r)
    {
        if(check(l, lx, r, rx))
        {
            ans += 2;
            lx = l;
            rx = r;
        }
        l++;
        r--;
    }
    if(lx + 1 != rx)ans++;

    cout << ans << '\n';

}   

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // open("in", "out");

    int t = 1;
    cin >> t;

    while(t--)
    {
        solve();
    }
}

Compilation message

palindromic.cpp: In function 'void open(std::string, std::string)':
palindromic.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".txt").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((f + ".txt").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 203 ms 18948 KB Output is correct
15 Correct 115 ms 18508 KB Output is correct
16 Correct 194 ms 18940 KB Output is correct
17 Correct 103 ms 12788 KB Output is correct