С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 08.06.2021
Сообщений: 1
1

Как можно оптимизировать программу?

08.06.2021, 21:52. Показов 384. Ответов 0

Author24 — интернет-сервис помощи студентам
Здравствуйте. Решил заняться олимпиадным программированием, и сейчас пытаюсь решить одну задачу. Далее следует ее краткое изложение:

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

В первой строке входных данных дано два целых числа n и q (https://www.cyberforum.ru/cgi-bin/latex.cgi?2\leq n\leq 1{10}^{5}, https://www.cyberforum.ru/cgi-bin/latex.cgi?1\leq q\leq 1{10}^{5}) — размер массива и количество запросов соответственно. Во второй строке дано n натуральных чисел, не превосходящих https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{9} — элементы массива. Далее следуют q строк, каждая из которых содержит два различных целых числа a и b (https://www.cyberforum.ru/cgi-bin/latex.cgi?1\leq a,b\leq n), означающих, что элементы массива с позициями a и b меняются местами.

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

Выведите q строк, являющимися ответами на запросы. Если после изменения позиций элементов ряд стал отсортированным по неубыванию, выведите "Sorted!". В противном случае выведите "Unsorted!". Кавычки выводить не нужно.

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int main() {
    unsigned int n, q;
    cin >> n >> q;
    long long a[n], b[n];
    int i,j;
    for (i = 0; i < n; i++) {
        long long y;
        cin >> y;
        a[i] = y;
        b[i] = y;
    }
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            if (b[i] > b[j]) {
                swap(b[i],b[j]);
            }
        }
    }
    int l, r;
 
    for (j = 0; j < q; j++) {
        cin >> l >> r;
        long long count = 0;
        swap(a[l-1],a[r-1]);
        for (i = 0; i < n; i++) {
            if (a[i] != b[i]) { count++;break; }
        }
        if (count > 0) { cout << "Unsorted!"<<endl; }
        else { cout << "Sorted!"<<endl; }
    }
}
Эта задача взята с муниципального этапа всероссийской олимпиады школьников по информатике в г.Адыгея. Я изложил лишь ее суть. В оригинале ограничение по времени 2 секунды, возможно такое же и в контесте. Своим решением я прохожу лишь 25 из 32 тестов, остальные выходят из лимита времени(Time limit exceeded). Помогите оптимизировать алгоритм.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
08.06.2021, 21:52
Ответы с готовыми решениями:

Как можно оптимизировать программу?
Здравствуй, Cyberforum. Долго копался в коде, но не вхожу во время) #include &lt;bits/stdc++.h&gt;...

Как можно оптимизировать код?
#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; int main() {...

Можно как-то оптимизировать этот код?
#include &lt;iostream&gt; using namespace std; int main() { unsigned int num, trueNum, a, howMany,...

Как можно оптимизировать данный код?
И... Ещё один вопрос: Дан участок кода С++: #include &lt;iostream&gt; #include &quot;Windows.h&quot; ...

0
08.06.2021, 21:52
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
08.06.2021, 21:52
Помогаю со студенческими работами здесь

Как можно оптимизировать решение данной задачи?
Всем привет! Есть задачка, вот условие: Напишите функцию, которая принимает в качестве...

Наследование классов как можно оптимизировать код и условие
Создал два класса родительский монстр и наследный демон. у демона появляется значение разум и...

Определить, что делает код, и как его можно оптимизировать
не могу понять что делает код . как его можно максимально сократить? #include &lt;iostream&gt; #include...

Кажется написал ужасный код. Можно его как-то оптимизировать?
Решал одну задачку: Даны натуральное число n, целые числа x 1 , ..., x n (все числа попарно...

Как оптимизировать программу ? Или подскажите другую реализацию. Задача на 47/1000 секунды превышает лимит
Найти и удалить (правым удалением), если существует, вершину с наибольшим ключом из вершин дерева,...

Как можно оптимизировать?
Подскажите пожалуйста. Имеется форма на которой находятся 20 edit'ов, как можно через цикл записать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Как программировать под HCL Notes и создавать свои продукты на ее основе
InfoMaster 11.01.2025
HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой мощную платформу для разработки корпоративных приложений, которая сочетает в себе функции электронной почты, календаря,. . .
Как работать с SVN (Subversion)
InfoMaster 11.01.2025
Введение Система контроля версий является неотъемлемой частью современного процесса разработки программного обеспечения. Она обеспечивает управление изменениями в коде, позволяет отслеживать. . .
Использование GraphQL в JavaScript
InfoMaster 11.01.2025
Введение в GraphQL и его преимущества В современной разработке веб-приложений эффективный обмен данными между клиентом и сервером играет ключевую роль. GraphQL представляет собой язык запросов и. . .
Администрирован­­­­ие Git, продвинутые техники работы с Git
InfoMaster 11.01.2025
Основы управления репозиторием Эффективное управление Git-репозиторием требует глубокого понимания механизмов контроля доступа и инструментов администрирования. Рассмотрим ключевые аспекты. . .
Что такое HCL Notes и как с ним работать
InfoMaster 10.01.2025
HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой комплексную платформу для совместной работы и обмена информацией в корпоративной среде. Это многофункциональное решение,. . .
Как работать с Git из Windows и Visual Studio
InfoMaster 10.01.2025
Работа с Git в Windows Работа с Git в операционной системе Windows может быть осуществлена с помощью различных инструментов, каждый из которых обладает своими уникальными возможностями и. . .
Аналог оператора switch case в Python
InfoMaster 10.01.2025
Оператор switch case используется в программировании для выбора одного из нескольких вариантов исполнения кода. Однако в языке Python этот оператор отсутствует. Понимание аналогов switch case в. . .
Отличия абстрактного класса от интерфейса
InfoMaster 10.01.2025
В современной разработке программного обеспечения существуют два основных механизма реализации абстракции: абстрактные классы и интерфейсы. Эти инструменты, хотя и схожи в своей основной цели -. . .
Как работать в Git
InfoMaster 10.01.2025
Git — это одна из наиболее популярных систем контроля версий, которая активно используется разработчиками по всему миру. Она позволяет эффективно управлять изменениями в коде, координировать работу. . .
Реализация передвижения персонажа в Unity3d на C#
InfoMaster 10.01.2025
Реализация передвижения персонажа в Unity3D начинается с правильной настройки проекта. Этот этап критически важен для создания отзывчивого и плавного управления. Рассмотрим основные шаги для создания. . .
Docker: руководство для начинающих
InfoMaster 10.01.2025
В современном мире разработки программного обеспечения контейнеризация стала неотъемлемой частью процесса создания и развертывания приложений. Docker, как ведущая платформа контейнеризации, произвела. . .
Книги и учебные ресурсы по C#
InfoMaster 08.01.2025
Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru