Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 2004.12.05;
Скачать: [xml.tar.bz2];

Вниз

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

 
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 вся ветка

Форум: "Потрепаться";
Текущий архив: 2004.12.05;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.45 MB
Время: 0.034 c
1-1100793569
kaktus
2004-11-18 18:59
2004.12.05
Кто рабол со словарями Word?


3-1099983586
mfender
2004-11-09 09:59
2004.12.05
MAX(id) из DELPHI


8-1094150415
AKM
2004-09-02 22:40
2004.12.05
Чем можно avi шки проигрывать, кроме TMediaPlayer a ?


1-1101001566
Bobby Digital
2004-11-21 04:46
2004.12.05
Listbox &amp; Edit


3-1100009021
gedd
2004-11-09 17:03
2004.12.05
btr файлы, чем открыть?





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский