Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Сортировка выбором

(Время: 1 сек. Память: 16 Мб Сложность: 24%)

В этой задаче вам предлагается реализовать сортировку выбором.

Задан массив целых чисел a0, a1, …, an−1. Отсортируем его следующим образом:

  • выберем наибольший элемент массива и поменяем его местами с последним элементом (если последний и есть найденный максимум, то обмен можно не совершать),
  • исключим из рассмотрения последний элемент и если длина оставшегося участка больше нуля перейдем опять к предыдущему пункту.

Таким образом, этот алгоритм состоит их n фаз, на каждой из которых выбирается максимум. Ваша задача реализовать эту сортировку описанным способом и вывести n чисел — индексы максимума на каждой из n фаз. Если максимум встречается более одного раза, то надо всегда выбирать первый из них.

Входные данные

В первой строке входного файла INPUT.TXT задано одно целое число n (1 ≤ n ≤ 1000) — количество элементов в массиве. Во второй строке задано n целых чисел через пробел: a0, a1, …, an−1 (|ai| ≤ 109) — элементы массива.

Выходные данные

В выходной файл OUTPUT.TXT выведите n чисел через пробел, где число i — это индекс первого максимального элемента на i-й фазе алгоритма.

Примеры

INPUT.TXTOUTPUT.TXT
15
40 30 20 40 20
0 3 1 0 0
23
1 2 3
2 1 0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Сортировка - 1
 Сортировка - 2
 A. Сортировка пузырьком
 B. Сортировка выбором
 C. Сортировка времени
 D. Выборы
 E. Лексикографический порядок чисел
 F. Свадьба
 G. Годовой баланс
 H. Рабочее время
 I. Маги
 J. Сортировка масс

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru