oj.uz

Submission #56834

# Submission time Handle Problem Language Result Execution time Memory
56834 2018-07-12T19:30:13 Z Mamnoon_Siam Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 46800 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

int n, m;
vector<string> ok, rev;
vector<int> v;

bool IsPrefix(string &s, string &pre) {
	if(pre.size() > s.size()) return false;
	for(int i = 0; i < pre.size(); i++) {
		if(pre[i] != s[i]) return false;
	} return true;
}

int32_t main () {
	// freopen("in", "r", stdin);
	cin >> n >> m;
	ok.resize(n), rev.resize(n);
	for(string &b : ok) cin >> b;
	sort(all(ok));
	for(int i = 0; i < n; i++) {
		rev[i] = ok[i];
		reverse(all(rev[i]));
		v.push_back(i);
	}
	sort(all(v), [](int x, int y){return rev[x] < rev[y];});
	sort(all(rev));

	// for(int i = 0; i < n; i++) cout << ok[i] << ' '; cout << endl;
	// for(int i = 0; i < n; i++) cout << rev[i] << ' '; cout << endl;
	// for(int i = 0; i < n; i++) cout << v[i] << ' '; cout << endl;

	while(m--) {
		int lo, hi;
		string pre, suf;
		cin >> pre >> suf;
		reverse(all(suf));
		int l = lower_bound(all(ok), pre) - ok.begin(), r;
		if(l >= ok.size() or !IsPrefix(ok[l], pre)) r = l - 1;
		else {
			lo = l, hi = ok.size() - 1;
			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(IsPrefix(ok[mid], pre)) {
					lo = mid + 1;
					r = mid;
				} else {
					hi = mid - 1;
				}
			}
		}
		int lit = lower_bound(all(rev), suf) - rev.begin(), rit;
		if(lit >= ok.size() or !IsPrefix(rev[lit], suf)) rit = lit - 1;
		else {
			lo = lit, hi = rev.size() - 1;
			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(IsPrefix(rev[mid], suf)) {
					lo = mid + 1;
					rit = mid;
				} else {
					hi = mid - 1;
				}
			}
		}
		// cout << "l = " << l << ", r = " << r << ", lit = " << lit << ", rit = " << rit << endl;
		int ret = 0;
		for(int i = lit; i <= rit; i++) {
			if(l <= v[i] and v[i] <= r)
				ret++;
		} cout << ret << endl;
	}
}

Compilation message

selling_rna.cpp: In function 'int myrand(int, int)':
selling_rna.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
selling_rna.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
selling_rna.cpp: In function 'bool IsPrefix(std::__cxx11::string&, std::__cxx11::string&)':
selling_rna.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pre.size(); i++) {
                 ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:66:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(l >= ok.size() or !IsPrefix(ok[l], pre)) r = l - 1;
      ~~^~~~~~~~~~~~
selling_rna.cpp:70:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:80:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lit >= ok.size() or !IsPrefix(rev[lit], suf)) rit = lit - 1;
      ~~~~^~~~~~~~~~~~
selling_rna.cpp:84:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:79:55: warning: 'rit' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int lit = lower_bound(all(rev), suf) - rev.begin(), rit;
                                                       ^~~
selling_rna.cpp:96:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(l <= v[i] and v[i] <= r)
       ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 420 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 3 ms 636 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 9528 KB Output is correct
2 Correct 278 ms 13716 KB Output is correct
3 Correct 300 ms 17728 KB Output is correct
4 Correct 297 ms 21712 KB Output is correct
5 Correct 177 ms 22348 KB Output is correct
6 Correct 198 ms 24932 KB Output is correct
7 Correct 346 ms 30556 KB Output is correct
8 Correct 361 ms 37644 KB Output is correct
9 Correct 339 ms 43364 KB Output is correct
10 Correct 333 ms 46800 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1544 ms 46800 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 420 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 3 ms 636 KB Output is correct
8 Correct 196 ms 9528 KB Output is correct
9 Correct 278 ms 13716 KB Output is correct
10 Correct 300 ms 17728 KB Output is correct
11 Correct 297 ms 21712 KB Output is correct
12 Correct 177 ms 22348 KB Output is correct
13 Correct 198 ms 24932 KB Output is correct
14 Correct 346 ms 30556 KB Output is correct
15 Correct 361 ms 37644 KB Output is correct
16 Correct 339 ms 43364 KB Output is correct
17 Correct 333 ms 46800 KB Output is correct
18 Execution timed out 1544 ms 46800 KB Time limit exceeded
19 Halted 0 ms 0 KB -