PKU 2081 Recaman's Sequence

PKU
  • Twitter上で@tozangezanさんがつぶやいていた問題
  • サイズが500000なのでO(N log N)のアルゴリズムまでなら通る可能性が高い
  • この回答では最初に500000まで求めてから、最後に入力を処理している
#include <iostream>
#include <set>

using namespace std;

static int a[500000 + 10];
int main() {
	set<int> used;
	for (int m = 0; m <= 500000; ++m) {
		if (a[m - 1] - m > 0 && !used.count(a[m - 1] - m)) {
			a[m] = a[m - 1] - m;
		} else {
			a[m] = a[m - 1] + m;
		}
		used.insert(a[m]);
	}

	for (int k; cin >> k && k != -1; ) {
		cout << a[k] << endl;
	}
}