oj.uz

답안 #51154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51154 2018-06-17T02:03:19 Z shoemakerjo Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 283 ms 36040 KB 
#include <bits/stdc++.h>

using namespace std;
#define maxn 100010
#define maxd 200010
#define pii pair<int, int>
#define insert trieadd
#define mp make_pair

//might need to double hash but whatever
const bool debug = false;
int N, M;
int BIT[maxn];
int ans[maxn]; //for printing b/c we do not compute in order
vector<pair< pair<string, string>, int>> cust; //customers
vector<vector<int>> activate(maxn); //indices of original guys
vector<vector<int>> deactivate(maxn);
vector<string> ostr;
int enc[27];
int endcust[maxn];
int endostr[maxn];

int trie[maxd][4]; //store indices
int tcind[maxd];
int numnodes = 1; //start at node 1

void insert(string cur, int ind) {
	++ind;
	int tmp = 1;
	for (int i = 0; i < cur.length(); i++) {
		int nx = enc[cur[i]-'A'];
		if (trie[tmp][nx]) {
			tmp = trie[tmp][nx];
			continue;
		}
		trie[tmp][nx] = ++numnodes;
		tmp = numnodes;
	}
	if (tcind[tmp] == 0) tcind[tmp] = ind;
}

vector<int> matches;

void qt(string cur) {
	int tmp = 1;
	for (int i = 0; i < cur.length(); i++) {
		int nx = enc[cur[i]-'A'];
		if (!trie[tmp][nx]) return;
		tmp = trie[tmp][nx];
		if (tcind[tmp]) matches.push_back(tcind[tmp]-1);
	}
}

int qu(int spot) {
	int ans = 0;
	while (spot > 0) {
		ans += BIT[spot];
		spot -= spot & (-spot);
	}
	return ans;
}

int query(int lo, int hi) {
	++hi;
	++lo;
	return qu(hi) - qu(lo-1);
}

void up(int ind, int diff) {
	while (ind < maxn) {
		BIT[ind] += diff;
		ind += ind & (-ind);
	}
}

void update(int ind, int diff) {
	++ind;
	up(ind, diff);
}

int main() {
	enc['A'-'A'] = 0;
	enc['C'-'A'] = 1;
	enc['G'-'A'] = 2;
	enc['U'-'A'] = 3;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	string cur;

	for (int i = 0; i < N; i++) {
		cin >> cur;
		string rev = "" + cur;
		reverse(rev.begin(), rev.end());
		ostr.push_back(rev);
	}
	sort(ostr.begin(), ostr.end()); //should be fast enough
	string pref, suf;
	for (int i = 0; i < M; i++) {
		cin >> pref >> suf;
		cust.push_back(mp(mp(pref, suf), i));
	}
	sort(cust.begin(), cust.end()); //should be fast enough

	if (debug) {
	cout << endl;
	cout << "asdfgfahafdsdvadfbashbasf OSTR" << endl;
	for (int i = 0; i < ostr.size(); i++) {
		cout << ostr[i] << endl;
	}
	cout << endl;

	cout << endl;
	for (int i = 0; i < cust.size(); i++) {
		cout << cust[i].first.first << " " << 
			cust[i].first.second <<
			 " " << cust[i].second << endl;
	}
	cout << endl;
	}
	
	vector<string> cp; //customer prefixes
	for (int i = 0; i < M; i++) {
		cp.push_back(cust[i].first.first);
	}

	endcust[cp.size()-1] = cp.size()-1;
	for (int i = cp.size()-2; i >= 0; i--) {
		if (cp[i] == cp[i+1]) {
			endcust[i] = endcust[i+1];
		}
		else endcust[i] = i;
	}

	endostr[ostr.size()-1] = ostr.size()-1;
	for (int i = ostr.size()-2; i >= 0; i--) {
		if (ostr[i] == ostr[i+1]) {
			endostr[i] = endostr[i+1];
		}
		else endostr[i] = i;
	}

	for (int i = 0; i < cp.size(); i++) {
		insert(cp[i], i);
	}

	for (int i = 0; i < ostr.size(); i++) {

		string rev = "" + ostr[i];
		reverse(rev.begin(), rev.end());

		matches.clear();
		qt(rev); //find all the prefix matches for this
		if (debug) cout << rev << " matches:" << endl;
		for (int val : matches) {
			activate[val].push_back(i);
			deactivate[endcust[val]+1].push_back(i);
			if (debug) 
				cout << "       " << val << " " << endcust[val] << endl; 
		}
	}

	//clear out the trie b/c why not
	numnodes = 1;
	for (int i = 0; i < maxd; i++) {
		trie[i][0] = trie[i][1] = trie[i][2] = trie[i][3] = 0;
		tcind[i] = 0;
	}

	// for (int i = 0; i < ostr.size(); i++) {
	// 	insert(ostr[i], i);
	// }

	if (debug) cout << endl << "----------------" << endl << endl;

	//looping through the M strings
	for (int i = 0; i < M; i++) {
		// cout << "i:   " << i << endl;
		for (int val : activate[i]) {
			// cout << "    adding in " << val << endl;
			update(val, 1);
		}
		for (int val : deactivate[i]) {
			// cout << "    taking out " << val << endl;
			update(val, -1);
		}
		int indo = cust[i].second;
		string suf = cust[i].first.second;
		//don't care at all about the prefix
		string rev = "" + suf;
		reverse(rev.begin(), rev.end());
		
		//then do my queries
		// matches.clear();
		// qt(rev);

		//maybe i want binary serach for this half
		int lo = 0;
		int hi = ostr.size()-1;
		int rl = rev.length();
		while (lo < hi) {
			int mid = (lo+hi)/2;

			if (ostr[mid].length() < rl) {
				if (rev < ostr[mid]) {
					hi = mid;
				}
				else lo = mid+1;
				continue;
			}

			if (rev > ostr[mid].substr(0, rl)) {
				lo = mid+1;
			}
			else {
				hi = mid;
			}
		}
		int qs = lo;
		if (ostr[qs].length() < rev.length() || 
			ostr[qs].substr(0, rev.length()) != rev) {
			if (debug) cout << rev << " DOES NOT MATCH" << endl;
			continue; //no match
		}		
		lo = 0;
		hi = ostr.size()-1;
		while (lo < hi) {
			int mid = (lo+hi+1)/2;

			if (ostr[mid].length() < rl) {
				if (rev < ostr[mid]) {
					hi = mid-1;
				}
				else lo = mid;
				continue;
			}

			if (rev < ostr[mid].substr(0, rl)) {
				hi = mid-1;
			}
			else {
				lo = mid;
			}
		}
		// cout << rev << " matches from " << lo << " to " << hi << endl;
		int qe = lo;
		if (debug) cout << rev << " matches from " << qs << " to " << qe << endl;
		ans[indo] = query(qs, qe);

		
	}
	for (int i = 0; i < M; i++) {
		cout << ans[i] << '\n';
	}
	cout.flush();
	cin >> N;



}
//don't think we actually need a hash, we can just bin search

Compilation message

selling_rna.cpp: In function 'void trieadd(std::__cxx11::string, int)':
selling_rna.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.length(); i++) {
                  ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void qt(std::__cxx11::string)':
selling_rna.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.length(); i++) {
                  ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ostr.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cust.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cp.size(); i++) {
                  ~~^~~~~~~~~~~
selling_rna.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ostr.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:204:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ostr[mid].length() < rl) {
        ~~~~~~~~~~~~~~~~~~~^~~~
selling_rna.cpp:230:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ostr[mid].length() < rl) {
        ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 9 ms 9060 KB Output is correct
3 Correct 9 ms 9136 KB Output is correct
4 Correct 9 ms 9212 KB Output is correct
5 Correct 9 ms 9288 KB Output is correct
6 Correct 9 ms 9288 KB Output is correct
7 Correct 11 ms 9304 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 28060 KB Output is correct
2 Correct 283 ms 36040 KB Output is correct
3 Correct 54 ms 36040 KB Output is correct
4 Correct 53 ms 36040 KB Output is correct
5 Runtime error 41 ms 36040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 36040 KB Output is correct
2 Correct 74 ms 36040 KB Output is correct
3 Correct 117 ms 36040 KB Output is correct
4 Correct 83 ms 36040 KB Output is correct
5 Correct 72 ms 36040 KB Output is correct
6 Correct 96 ms 36040 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 9 ms 9060 KB Output is correct
3 Correct 9 ms 9136 KB Output is correct
4 Correct 9 ms 9212 KB Output is correct
5 Correct 9 ms 9288 KB Output is correct
6 Correct 9 ms 9288 KB Output is correct
7 Correct 11 ms 9304 KB Output is correct
8 Correct 168 ms 28060 KB Output is correct
9 Correct 283 ms 36040 KB Output is correct
10 Correct 54 ms 36040 KB Output is correct
11 Correct 53 ms 36040 KB Output is correct
12 Runtime error 41 ms 36040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -