Олимпиадная школьная задача про последовательность.

[Fsb4000]

Вот текст задачи:
Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535).В i-й из N последующих строк записано целое число Ki—номер позиции в последовательности (1 ≤ Ki ≤ $2^{31} $-1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
Ограничения: по времени 1с; по памяти 16 mb.
Вот мое решение:

Используется синтаксис C++

#include<iostream>
#include<cstdlib>

using namespace std;

int cmp(const void*a, const void*b){
        return (*(long*)a-*(long*)b);
}

int main(void){
        long N,A,i,k,l,m=0;
        long *b;
        char *a;
        k=0;l=0;
        cin>>N;
        b=new long[N];
        a=new char[N];
        for(i=0;i<N;i++){
                cin>>b[i];
        }
        qsort(b,N,sizeof(long),cmp);
        for(i=0;i<2147483648-1;i++){
                if(k==l) {k++;l=0;if(b[m]==i+1){a[m]=1;m++;if(m==N) break;}}
                else if(b[m]==i+1){a[m]=0;m++;if(m==N) break;}
                l++;
        }
        for(i=0;i<N;i++){
                if(i!=N-1){cout<<(int)a[i]<<" ";}
                else {cout<<(int)a[i];}
        }
        cout<<endl;
        system("pause");
        return 0;
}
 

То есть я строю последоватьность до наибольшего номера позиции которую нужно вывести.
Можно ли как то улучшить такой алгоритм? А то Time limit exceeded, при больших Ki.
Если нельзя, то как дойти до такого :

a:=(sqrt(8*b-7)-1)/2;
if (frac(a)<eps) or (frac(a)>1-eps) then write('1 ')
else write('0 ');

[Toucan]

Fsb4000, у нас на форуме запрещено обсуждение заданий ещё не закончившихся заочных и онлайн олимпиад.
Из какой олимпиады Вы взяли Вашу задачу?

[Fsb4000]

http://acm.timus.ru/problem.aspx?space=1&num=1209

[Toucan]

Спасибо, можно обсуждать :)

[Xaositect]

Сумма арифметической прогрессии.
Посчитайте, на каком месте стоит $k$-я единица.

[Fsb4000]

Xaositect спасибо.
То есть у нас стоят единички на 0,1,3,6,10....
то есть:

$$K_i-1=0+1+2+...+n=\frac{n(n+1)}{2}$$

$$n^2+n-2K_i-2=0$$

$$D=1+4(2K_i-2)=8K_i-7$$

$n=\frac{-1+\sqrt{8K_i-7}}{2}$---n должно быть целым->так как $8K_i-7$ нечетное, и корень нечетного нечетное(если целое), то для того чтобы n было целым достаточно проверить, что $\sqrt{8K_i-7}$ целый.

Изменил свою программу так:

Используется синтаксис C++

 
#include<iostream>
#include<cstdlib>

using namespace std;


int main(void){
        long N;
        long *b;
        long i;
        long double m;
        cin>>N;
        b=new long[N];
        for(i=0;i<N;i++){
                cin>>b[i];
        }
        for(i=0;i<N;i++){
                m=sqrt(long double(8.0*long double(b[i])-7.0));
                if(fabs(m-ceil(m))<0.00001){
                        if(i!=N-1){
                                cout<<"1"<<" ";
                        }
                        else{
                                cout<<"1";
                        }
                }
                else {
                        if(i!=N-1){
                                cout<<"0"<<" ";
                        }
                        else{
                                cout<<"0";
                        }
                }
        }
        cout<<endl;
        system("pause");
        return 0;
}
 

Выдает Wrong Answer Test №3.(раньше на нем timelimit был )
(писал вместо ceil, и long и floor-результат тот же)
UPD. толи я ночью нечего не соображал, но сейчас засчитали задачу.
изменил m на $\sqrt{8K_i-7}$, было $\frac{-1+\sqrt{8K_i-7}}{2}$
Еще раз спасибо Xaositect