oj.uz

Submission #742066

# Submission time Handle Problem Language Result Execution time Memory
742066 2023-05-15T14:13:01 Z GrindMachine Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 88316 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> ps = {5791, 8237, 3067, 6991, 3527};
vector<int> mods = {791139137, 433567597, 271149607, 561259969, 222708581};
ll pows[N][2];

void precalc() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    shuffle(all(ps), rng);
    shuffle(all(mods), rng);

    rep(j, 2) {
        pows[0][j] = 1;
        rep1(i, N - 1) {
            pows[i][j] = pows[i - 1][j] * ps[j] % mods[j];
        }
    }
}

struct Hash {
    ll a[2];

    Hash() {
        memset(a, 0, sizeof a);
    }

    Hash(ll x, ll y) {
        a[0] = x, a[1] = y;
    }

    Hash operator+(char ch) {
        Hash b;
        ll x = ch - 'A' + 1;

        rep(j, 2) {
            b.a[j] = (a[j] * ps[j] + x) % mods[j];
        }

        return b;
    }

    Hash operator-(Hash h) {
        Hash b;
        rep(j, 2) {
            b.a[j] = (a[j] - h.a[j] + mods[j]) % mods[j];
        }

        return b;
    }

    Hash poww(ll k) {
        Hash b;
        rep(j, 2) {
            b.a[j] = a[j] * pows[k][j] % mods[j];
        }

        return b;
    }

    bool operator==(Hash h) {
        rep(j, 2) {
            if (a[j] != h.a[j]) {
                return false;
            }
        }

        return true;
    }

    bool operator<(const Hash &h) const {
        rep(j, 2) {
            if (a[j] != h.a[j]) {
                return a[j] < h.a[j];
            }
        }

        return false;
    }
};

void solve(int test_case)
{
    precalc();

    ll n, m; cin >> n >> m;
    vector<vector<Hash>> pref_hashes(n), suff_hashes(n);

    rep(i, n) {
        string s; cin >> s;
        Hash hsh;
        rep(j, sz(s)) {
            hsh = hsh + s[j];
            pref_hashes[i].pb(hsh);
        }

        hsh = Hash();

        rev(j, sz(s) - 1, 0) {
            hsh = hsh + s[j];
            suff_hashes[i].pb(hsh);
        }
    }

    while (m--) {
        string p, q; cin >> p >> q;
        ll siz1 = sz(p), siz2 = sz(q);
        reverse(all(q));

        Hash hsh1, hsh2;
        trav(ch, p) hsh1 = hsh1 + ch;
        trav(ch, q) hsh2 = hsh2 + ch;

        ll ans = 0;

        rep(i, n) {
            ll siz = sz(pref_hashes[i]);
            if (siz < max(siz1, siz2)) conts;

            if (hsh1 == pref_hashes[i][siz1 - 1] and hsh2 == suff_hashes[i][siz2 - 1]) {
                ans++;
            }
        }

        cout << ans << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'void solve(int)':
selling_rna.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
      |                                    ^
selling_rna.cpp:151:9: note: in expansion of macro 'rep'
  151 |         rep(j, sz(s)) {
      |         ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 79004 KB Output is correct
2 Correct 403 ms 86124 KB Output is correct
3 Correct 280 ms 82868 KB Output is correct
4 Correct 294 ms 86232 KB Output is correct
5 Correct 298 ms 57420 KB Output is correct
6 Correct 315 ms 58012 KB Output is correct
7 Correct 247 ms 64532 KB Output is correct
8 Correct 401 ms 88316 KB Output is correct
9 Correct 355 ms 88304 KB Output is correct
10 Correct 651 ms 85900 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 9320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1892 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 3 ms 1892 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 167 ms 79004 KB Output is correct
9 Correct 403 ms 86124 KB Output is correct
10 Correct 280 ms 82868 KB Output is correct
11 Correct 294 ms 86232 KB Output is correct
12 Correct 298 ms 57420 KB Output is correct
13 Correct 315 ms 58012 KB Output is correct
14 Correct 247 ms 64532 KB Output is correct
15 Correct 401 ms 88316 KB Output is correct
16 Correct 355 ms 88304 KB Output is correct
17 Correct 651 ms 85900 KB Output is correct
18 Execution timed out 1554 ms 9320 KB Time limit exceeded
19 Halted 0 ms 0 KB -