oj.uz

Submission #343269

# Submission time Handle Problem Language Result Execution time Memory
343269 2021-01-03T15:30:46 Z Millad Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 46 ms 25872 KB 
// In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 1e5 + 6, inf = 1e18, mod = 1e9 + 7, mod2 = 1e9 + 9;
ll n, m, pw26[2][maxn];
str s[maxn], t[maxn];
vector <ll> v[2][maxn];
void hAsh(int k){
	int sz = s[k].size();
	for(int i = 0; i < sz; i ++){
		ll c = s[k][i] - 'A';
		v[0][k].pb(c * pw26[0][i] % mod);
		v[1][k].pb(c * pw26[1][i] % mod2);
		if(i > 0)(v[0][k][i] += v[0][k][i - 1]) %= mod;
		if(i > 0)(v[1][k][i] += v[1][k][i - 1]) %= mod2;
	}
}
pll HASH(int k){
	int sz = t[k].size();
	ll x = 0, x2 = 0;
	for(int i = 0; i < sz; i ++){
		ll c = t[k][i] - 'A';
		(x += c * pw26[0][i] % mod) %= mod;
		(x2 += c * pw26[1][i] % mod2) %= mod2;
	}
	pll pr = {x, x2};
	return pr;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw26[0][0] = 1;
	pw26[1][0] = 1;
	ll z = 26;
	for(int i = 1; i < maxn; i ++){
		pw26[0][i] = (pw26[0][i - 1] * z % mod);
		pw26[1][i] = (pw26[1][i - 1] * z % mod2);
	}
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i ++){
		scanf("%s", &s[i]);
		hAsh(i);
	}
	for(int i = 0; i < m; i ++){
		scanf("%s%s", &t[i * 2], &t[i * 2 + 1]);
		pll p1 = HASH(i * 2);
		pll p2 = HASH(i * 2 + 1);
		ll ans = 0;
		for(int j = 0; j < n; j ++){
			if(s[j].size() < t[i * 2].size())continue;
			if(s[j].size() < t[i * 2 + 1].size())continue;
			if(v[0][j][t[i * 2].size() - 1] != p1.F)continue;
			if(v[1][j][t[i * 2].size() - 1] != p1.S)continue;
			ll x = v[0][j][s[j].size() - 1];
			int szj = s[j].size();
			int szq = t[i * 2 + 1].size();
			int dif = szj;
			dif -= szq;
			if(dif)x = (x - v[0][j][dif - 1] + mod) % mod;
         if((p2.F * pw26[0][dif] % mod) != x)continue;
			x = v[1][j][s[j].size() - 1];
			if(dif)x = (x - v[1][j][dif - 1] + mod2) % mod2;
			if((p2.S * pw26[1][dif] % mod2) != x)continue;
			ans ++;
		}
		cout << ans << "\n";
	}
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:52:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   52 |  scanf("%d%d", &n, &m);
      |         ~^     ~~
      |          |     |
      |          int*  ll* {aka long long int*}
      |         %lld
selling_rna.cpp:52:12: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   52 |  scanf("%d%d", &n, &m);
      |           ~^       ~~
      |            |       |
      |            int*    ll* {aka long long int*}
      |           %lld
selling_rna.cpp:54:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'str*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
   54 |   scanf("%s", &s[i]);
      |          ~^   ~~~~~
      |           |   |
      |           |   str* {aka std::__cxx11::basic_string<char>*}
      |           char*
selling_rna.cpp:58:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'str*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
   58 |   scanf("%s%s", &t[i * 2], &t[i * 2 + 1]);
      |          ~^     ~~~~~~~~~
      |           |     |
      |           char* str* {aka std::__cxx11::basic_string<char>*}
selling_rna.cpp:58:13: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'str*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
   58 |   scanf("%s%s", &t[i * 2], &t[i * 2 + 1]);
      |            ~^              ~~~~~~~~~~~~~
      |             |              |
      |             char*          str* {aka std::__cxx11::basic_string<char>*}
selling_rna.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%s", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~
selling_rna.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%s%s", &t[i * 2], &t[i * 2 + 1]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 25836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 25836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 25872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 25836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -