oj.uz

Submission #552008

# Submission time Handle Problem Language Result Execution time Memory
552008 2022-04-22T07:27:09 Z Arnch Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 227844 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 2e6 + 10, mod = 1e9 + 9, pr = 1000696969, Log = 30;

string s[N], t;
int Rank[N][Log], p[N], cnt[N], ans[N], bon[N], n, m, lg;
vector<int> sp[N], sf[N];
vector<pair<int, int> > query[N];
map<int, pair<int, int> > mp;
map<int, int> nu;


/*bool cmp(int i, int j) {
	int l = 0, r = min(Sz(s[i]), Sz(s[j])), mid;
	while(l < r - 1) {
		mid = (l + r) >> 1;
		if(sp[i][mid] == sp[j][mid]) {
			l = mid;
			continue;
		}
		r = mid;
	}
	if(l == n) return i < j;
	return s[i][l + 1] < s[j][l + 1];
}*/

bool cmp(int i, int j) {
	if(Rank[i][lg - 1] != Rank[j][lg - 1]) return Rank[i][lg - 1] < Rank[j][lg - 1];
	if(j + (1 << (lg - 1)) > bon[j]) return 1;
	if(i + (1 << (lg - 1)) > bon[i]) return 0;
	return Rank[i + (1 << (lg - 1))][lg - 1] < Rank[j + (1 << (lg - 1))][lg - 1];
}

void build() {
	t = "";
	for(int i = 1; i <= n; i++) {
		for(auto c : s[i]) t.push_back(c);
	}

	int pos = 0;
	for(int i = Sz(t) - 1; i >= 0; i--) {
		if(t[i] == '#') pos = i;
		bon[i] = i;
	}

	for(int i = 0; i < Sz(t); i++) p[i] = i, Rank[i][0] = t[i];
	for(lg = 1; lg < Log; lg++) {
		sort(p, p + Sz(t), cmp);
		Rank[p[0]][lg] = 0;
		for(int j = 1; j < Sz(t); j++) {
			Rank[p[j]][lg] = Rank[p[j - 1]][lg] + cmp(p[j - 1], p[j]);
		}
	}
}

bool cmp2(pair<int, int> i, pair<int, int> j) {
	return Rank[i.first][lg] < Rank[j.first][lg];
}


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

	cin >>n >>m;
	for(int i = 1; i <= n; i++) cin >>s[i], s[i] = '#' + s[i];
	
	ll val = 0;
	for(int i = 1; i <= n; i++) {
		sp[i].resize(Sz(s[i]) + 5);
		val = 0;
		for(int j = 1; j < Sz(s[i]); j++) {
			val *= pr, val += (s[i][j] - 'A' + 1);
			val %= mod;
			sp[i][j] = val;
		}
		sf[i].resize(Sz(s[i]) + 5);
		val = 0;
		for(int j = Sz(s[i]) - 1; j > 0; j--) {
			val *= pr, val += (s[i][j] - 'A' + 1);
			val %= mod;
			sf[i][Sz(s[i]) - j] = val;
		}
	}
/*
	build();

	vector<int> vc;
	for(int i = 1; i <= n; i++) vc.push_back(i);

	sort(All(vc), cmp);


	vector<int> vc;
	vector<pair<int, int> > st;
	int sum = 1;
	for(int i = 1; i <= n; i++) {
		st.push_back({sum, i});
		sum += Sz(s[i]);
	}
	sort(All(st), cmp2);

	for(auto i : st) vc.push_back(i.second);

	
	
	for(int i = 0; i < n; i++) {
		ll val = 0;
		for(int j = 1; j < Sz(s[vc[i]]); j++) {
			val *= pr, val += (s[vc[i]][j] - 'A'+ 1);
			val %= mod;
			if(mp[val].first == 0) mp[val].first = i + 1;
			mp[val].second = i + 1;
		}
	}
*/

	for(int i = 0; i < m; i++) {
		string A, B; cin >>A >>B;
		ll valA = 0, valB = 0;
		for(int j = 0; j < Sz(A); j++) {
			valA *= pr, valA += (A[j] - 'A' + 1);
			valA %= mod;
		}
		for(int j = Sz(B) - 1; j >= 0; j--) {
			valB *= pr, valB += (B[j] - 'A' + 1);
			valB %= mod;
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			if(Sz(A) >= Sz(s[i]) || Sz(B) >= Sz(s[i])) continue;
			if(sp[i][Sz(A)] == valA && sf[i][Sz(B)] == valB) ans++; 
		}
		cout<<ans <<endl;
	}




    return 0;
}

Compilation message

selling_rna.cpp: In function 'void build()':
selling_rna.cpp:59:6: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   59 |  int pos = 0;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 203828 KB Output is correct
2 Correct 92 ms 203788 KB Output is correct
3 Correct 105 ms 203932 KB Output is correct
4 Correct 96 ms 203736 KB Output is correct
5 Correct 91 ms 203812 KB Output is correct
6 Correct 92 ms 203748 KB Output is correct
7 Correct 91 ms 203724 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 221660 KB Output is correct
2 Correct 310 ms 225896 KB Output is correct
3 Correct 232 ms 225608 KB Output is correct
4 Correct 251 ms 225996 KB Output is correct
5 Correct 250 ms 217652 KB Output is correct
6 Correct 258 ms 217904 KB Output is correct
7 Correct 220 ms 222620 KB Output is correct
8 Correct 300 ms 227844 KB Output is correct
9 Correct 262 ms 227660 KB Output is correct
10 Correct 338 ms 225356 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 203828 KB Output is correct
2 Correct 92 ms 203788 KB Output is correct
3 Correct 105 ms 203932 KB Output is correct
4 Correct 96 ms 203736 KB Output is correct
5 Correct 91 ms 203812 KB Output is correct
6 Correct 92 ms 203748 KB Output is correct
7 Correct 91 ms 203724 KB Output is correct
8 Correct 164 ms 221660 KB Output is correct
9 Correct 310 ms 225896 KB Output is correct
10 Correct 232 ms 225608 KB Output is correct
11 Correct 251 ms 225996 KB Output is correct
12 Correct 250 ms 217652 KB Output is correct
13 Correct 258 ms 217904 KB Output is correct
14 Correct 220 ms 222620 KB Output is correct
15 Correct 300 ms 227844 KB Output is correct
16 Correct 262 ms 227660 KB Output is correct
17 Correct 338 ms 225356 KB Output is correct
18 Execution timed out 1601 ms 208544 KB Time limit exceeded
19 Halted 0 ms 0 KB -