名前が既出かどうかの判定を毎回愚直に行おうとすると，全体で最悪 \(\Theta(Q^2)\) 時間かかることになり，これを通すのは現実的ではありません．なので，より効率の良い方法を考えることになります．

この問題は，連想配列と呼ばれるデータ構造を使うことで解けます．連想配列についての説明は本解説では省略します．

空の連想配列 \(\mathrm{accounts} := \emptyset\) と，既存の ID の最大値 \(\mathrm{idmax} := 0\) を用意します．連想配列 \(\mathrm{accounts}\) の内容として，名前をキーに，対応する ID を値にして格納することを考えます．

各クエリでは，以下の処理を行えばよいです．

• 連想配列　\(\mathrm{accounts}\) に，\(s\) がキーとして含まれるかを判定する．
  • 含まれるならば，対応する値を出力する．
  • 含まれないならば，\(\mathrm{idmax}\) を \(1\) 増やし，\((s, \mathrm{idmax})\) をキー・値ペアとして \(\mathrm{accounts}\) に格納する．その後，\(\mathrm{idmax}\) を出力する．

一般的な連想配列の実装では，参照・追加ともに \(O(\log n)\) 時間で行えます(\(n\) は連想配列のサイズ)．よってこの問題は \(O(Q \log Q)\) 時間で解くことができ，十分高速です．

実装例 (C++)

多くのプログラミング言語においては連想配列が標準機能として提供されています．たとえば C++ では std::map を，Python では dict を使用できます．

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <string>
using std::string;
#include <map>
using std::map;

int main (void) {
	int q;
	cin >> q;

	map<string, int> accounts;
	int idmax = 0;
	for (int qi = 0; qi < q; qi++) {
		string s;
		cin >> s;

		int ans;
		if (accounts.contains(s)) {
			ans = accounts[s];
		} else {
			ans = accounts[s] = ++idmax;
		}

		cout << ans << "\n";
	}
	
	return 0;
}