oj.uz

Submission #318164

# Submission time Handle Problem Language Result Execution time Memory
318164 2020-10-31T14:35:56 Z Return_0 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 105 ms 26236 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("Ofast")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef LOCAL
#define dbg(x) cout<< #x << " : " << x << endl
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1);
#else
#define dbg(x) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define mid ((l + r) / 2)
#define All(x) (x).begin(), (x).end()

const long long inf = 1e18;
cl mod = 1e9 + 7, MOD = 998244353;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out << '(' << a.first << ", " << a.second << ')';    }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
    if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e6 + 7, Base = 29, SIGMA = 26, md [2] = {mod, 1100000123};

struct Hash
{
    ll x, y;

    Hash (ll A = 0, ll B = 0) {   x = A, y = B; }

    void push_front (cl &x) {   *this = (((*this) * Base) + Hash(x, x)); }

    void push_back (cl &x, const Hash &val) {   *this = (val * x) + (*this);    }

    friend Hash operator * (const Hash &X, cl &y) {
        Hash ret;

        ret.x = (ll(X.x) * y) % md[0];
        ret.y = (ll(X.y) * y) % md[1];

        return ret;
    }

    friend Hash operator * (const Hash &X, const Hash &Y) {
        Hash ret;

        ret.x = (ll(X.x) * Y.x) % md[0];
        ret.y = (ll(X.y) * Y.y) % md[1];

        return ret;
    }

    friend Hash operator + (const Hash &X, const Hash &Y) {
        Hash ret;

        ret.x = (ll(X.x) + Y.x) % md[0];
        ret.y = (ll(X.y) + Y.y) % md[1];

        return ret;
    }

    friend Hash operator - (const Hash &X, const Hash &Y) {
        Hash ret;

        ret.x = (ll(X.x) - Y.x + md[0]) % md[0];
        ret.y = (ll(X.y) - Y.y + md[1]) % md[1];

        return ret;
    }

    friend bool operator == (const Hash &X, const Hash &Y)  {   return (X.x == Y.x && X.y == Y.y);  }
};

string s;
Hash pw [N];

int main ()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    ll i, j, l, r, ans, n, t;
    Hash perf, suff;

    pw[0].x = pw[0].y = 1;
    for (i = 1; i < N; i++) pw[i] = pw[i-1] * Base;

    cin>> t;

    while (t--) {
        ans = 0;
        cin>> s;
        n = SZ(s);

        perf = suff = Hash();

        for (l = 0, r = n-1, j = 0; l < r; l++, r--, j++) {
            perf.push_front(s[l] - 'a' + 1);
            suff.push_back(s[r] - 'a' + 1, pw[j]);

            if ((suff == perf)) {
                ans += 2;
                j = -1;
                perf = suff = Hash();
            }
        }

        if ((perf.x && perf.y) || (l == r))   ans++;

        cout<< ans << '\n';
    }

    // cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

    return 0;
}
/*
4
bonobo
deleted
racecar
racecars

*/

Compilation message

palindromic.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
palindromic.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
      |     ^~
palindromic.cpp:38:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |     if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
      |                                    ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15980 KB Output is correct
2 Correct 16 ms 15980 KB Output is correct
3 Correct 16 ms 15980 KB Output is correct
4 Correct 16 ms 15980 KB Output is correct
5 Correct 16 ms 15980 KB Output is correct
6 Correct 15 ms 15980 KB Output is correct
7 Correct 16 ms 15980 KB Output is correct
8 Correct 16 ms 15980 KB Output is correct
9 Correct 16 ms 15980 KB Output is correct
10 Correct 16 ms 15980 KB Output is correct
11 Correct 17 ms 15980 KB Output is correct
12 Correct 17 ms 15980 KB Output is correct
13 Correct 17 ms 15980 KB Output is correct
14 Correct 105 ms 23680 KB Output is correct
15 Correct 67 ms 22272 KB Output is correct
16 Correct 100 ms 26236 KB Output is correct
17 Correct 68 ms 21888 KB Output is correct