Скачать: CL | DM;

Не поможите ли с олимпиадной задачей?   Найти похожие ветки 

← →
DillerXX ©   (2004-11-06 10:29) [0]

Вот сам текст:

Была дана перестановка, по ней построили таблицу инверсий. Восстановите перестановку.

Входные данные
В первой строке входного файла записано число N (1 <= N <= 100000). Далее, во второй строке, следуют N целых чисел A1, A2, ..., AN, где число Ak (0 <= Ak < N) означает,
что ровно Ak элементов, больших чем k, стоит до числа k в перестановке.

Выходные данные
Выведите искомую перестановку.

Пример

Ввод
4
2 0 1 0

Вывод
2 4 1 3


Наш уважаемый Neoff решил её, но к сожалению, при больших N она не укладывается по времени на 200 миллисекунд :( (на тест 1 секунда). На всякий случай привожу код:

program z127;
var b:array[1..100000] of integer;
   i,j,n,a,k:integer;
begin
    Assign(input,"Input.txt"); Reset(input);
    Assign(output,"output.txt"); Rewrite(output);
    readln(n);
    fillchar(b,sizeof(b),0);
    for i:=1 to n do begin
        read(a);
        j:=0;
        for k:=1 to n do begin
            if b[k]=0 then begin
               if j=a then begin b[k]:=i; break; end;
               inc(j);
            end;
        end;
    end;
    for i:=1 to n do write(b[i]," ");
end.


Может кто-нибудь сделать так чтобы по времени всё проходило? ИМХО тут надо его полностью менять...
Заранее спасибо.

---

← →
DillerXX ©   (2004-11-06 12:51) [1]

ыы ну может поможет всё таки кто-нибудь :\

---

← →
123 ©   (2004-11-06 13:04) [2]

А как ты меряешь время?

---

← →
Vasya.ru ©   (2004-11-06 15:22) [3]

а не с саратовской заочной олимпиады задачка? Так там их 300 штук будет, и ты с каждой сюда ломится будешь?

---

← →
SergP.   (2004-11-06 15:39) [4]

А что такое таблица инверсий?

---

← →
Мирзаянов М.   (2004-11-15 22:19) [5]

http://acm.sgu.ru/univer/problem.php?contest=0&problem=126
http://acm.sgu.ru/univer/problem.php?contest=0&problem=127

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.022 c