Timus-1209 : 1, 10, 100, 1000...

問題概要

11010010001000010...という文字列のi文字目が何か答える問題。クエリ数Q(<5*10^4)、iの上限L=2^31。

解法

1,2,4,7,11,16,..という数列をあらかじめ持っておいて各クエリには二分探索で処理をする。

acceptされたコード

計算量O(sqrt(L) + Q * logL)。

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int64;

int main(){
	vector<int64> ones;
	ones.push_back(1);
	for(int i=1; ones.back() < (1LL<<31);i++){
		ones.push_back(ones.back() + i);
	}

	int N;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int64 x;
		scanf("%lld", &x);
		printf("%d%c", binary_search(ones.begin(), ones.end(), x)?1:0, i==N-1?'\n':' ');
	}

	return 0;
}