まずは「ハッシュ」という言葉をスルーしてそのまま書いた場合。これは時間切れになります。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<string> dictionary; dictionary.reserve(1000000); string command, str; for (int i = 0; i < n; i++) { cin >> command >> str; if (command[0] == 'i') { dictionary.push_back(str); } else { const bool found = (dictionary.end() != find(dictionary.begin(), dictionary.end(), str)); cout << (found ? "yes" : "no") << endl; } } return 0; }
先頭文字で辞書を分けてみたのがこれ。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; static vector<string> dicA, dicC, dicG, dicT; static inline vector<string>& getDictionary(char first) { switch (first) { case 'A': return dicA; case 'C': return dicC; case 'G': return dicG; case 'T': default: return dicT; } } int main() { int n; cin >> n; string command, str; for (int i = 0; i < n; i++) { cin >> command >> str; auto& dic = getDictionary(str[0]); if (command[0] == 'i') { dic.push_back(str); } else { const bool found = (dic.end() != find(dic.begin(), dic.end(), str)); cout << (found ? "yes" : "no") << endl; } } return 0; }
数秒ほど早くなりましたが、やはり最後は時間切れになります。文字列の比較とかやってるので当たり前という気はします。