Submission #1244208

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

unordered_map<char, int> currentOrder;

struct comp {
	bool operator() (string a, string b) {
		int i = 0, j = 0;
		while (a[i] == b[j]) {
			++i;
			++j;
			if (i == a.length() || j == b.length()) {
				break;
			}
		}
		if (i == a.length() || j == b.length()) {
			return a.length() < b.length();
		} else {
			return currentOrder[a[i]] < currentOrder[b[j]];
		}
	}
} comp;

int find(vector<string> &str, string s) {
	int l = 0, r = str.size() - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (comp(str[mid], s)) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	return l;
}

int main(void) {

	ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<string> str(n);
	for (int i = 0; i < n; ++i) {
		cin >> str[i];
	}

	int q; cin >> q;
	vector<int> result(q, -1);
	unordered_map< string, vector< pair<string, int> > > table;
	for (int i = 0; i < q; ++i) {
		int idx;
		string order;
		cin >> idx >> order;
		table[order].push_back(make_pair(str[idx - 1], i));
	}

	unordered_map< string, vector< pair<string, int> > >::iterator iter;
	for (iter = table.begin(); iter != table.end(); ++iter) {
		string order = iter->first;
		for (int i = 0; i < 26; ++i) {
			currentOrder[order[i]] = i;
		}
		sort(str.begin(), str.end(), comp);
		/*
		for (int i = 0; i < str.size(); ++i) {
			cout << str[i] << endl;
		}
		cout << endl;
		*/
		for (int i = 0; i < iter->second.size(); ++i) {
			result[iter->second[i].second] = find(str, iter->second[i].first) + 1;
		}
		// break;
	}

	for (int i = 0; i < q; ++i) {
		cout << result[i] << endl;
	}
	return 0;

}

Submission Info

Judge Result