oj.uz

Submission #318158

# Submission time Handle Problem Language Result Execution time Memory
318158 2020-10-31T14:29:57 Z Return_0 Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 34 ms 12288 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 = 2e5 + 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 4 ms 3436 KB Output is correct
2 Correct 4 ms 3436 KB Output is correct
3 Correct 4 ms 3436 KB Output is correct
4 Correct 4 ms 3436 KB Output is correct
5 Correct 4 ms 3436 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 40.0

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