|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
||||||
Уменьшение времени работы программы01.11.2013, 16:24. Показов 2153. Ответов 17
Метки нет (Все метки)
Добрый вечер. Решил задачу, и решил прогнать по acmp.ru. Программа заваливается по времени выполнения, выходит 2.5 секунд, в идеале должно быть не меньше одной. Помогите плиз.
Вот задача: Кликните здесь для просмотра всего текста
Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом: сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников со сторонами, параллельными сторонам холста и вершинами, расположенными в целочисленных координатах. Помогите художнику определить площадь незакрашенной части холста. Входные данные Первая строка входного файла INPUT.TXT содержит два натуральных числа w и h (1 ≤ w, h ≤ 100). Во второй строке записано целое число n (0 ≤ n ≤ 5000) – количество прямоугольников. Следующие n строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2 , где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно. Выходные данные Выведите в выходной файл OUTPUT.TXT одно целое число – площадь незакрашенной части холста. Вот Код: Кликните здесь для просмотра всего текста
0
|
||||||
| 01.11.2013, 16:24 | |
|
Ответы с готовыми решениями:
17
Ограничение по времени работы программы |
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
||||||||||||||||
| 01.11.2013, 18:20 | ||||||||||||||||
|
Слишком много циклов. подсчитывать занятые можно и в первом:
А еще (хз, мож тут и не заметно будет) можно развернуть матрицу в массив(т.е. память выделять один раз), и обращаться как [I] a[j] -> a[j*width+i]. Опять же, на таких данных может прироста и не заметишь...хотя по идее при больших размерах массива это будет быстрее(выделение памяти чертовски накладная операция) Ах да, инициализацию можно занести туда:
1
|
||||||||||||||||
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
| 01.11.2013, 19:05 [ТС] | |
|
0
|
|
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|||||||||||
| 01.11.2013, 19:16 | |||||||||||
|
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
Добавлено через 57 секунд Ну, это не означает, что время уменьшилось) Погрешность просто... Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
1
|
|||||||||||
|
Форумчанин
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
|
| 01.11.2013, 19:27 | |
|
0
|
|
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|||
| 01.11.2013, 19:34 [ТС] | |||
|
Добавлено через 2 минуты
0
|
|||
|
Форумчанин
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
|
| 01.11.2013, 19:44 | |
|
vector<char> будет работать быстрее всех его специализаций. Но если честно, не за чем тут усложнять обычный двумерный массив.
Добавлено через 50 секунд
0
|
|
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
| 01.11.2013, 19:48 [ТС] | |
|
0
|
|
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
| 01.11.2013, 19:52 | |
|
а ларчик то просто открывается: в задаче сказано, что данные должны читаться из файла INPUT.txt и записываться в OUTPUT.txt. у вас они читаются из cin, а записываются в cout, а система ищет файл OUTPUT.txt
1
|
|
|
Модератор
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
|
||||||||||||
| 01.11.2013, 20:04 | ||||||||||||
|
Инспектор Котик,
у тебя алгоритм не тот во первых ты выделяешь память при максиме это 101 одно выделение памяти потом 10000 обращений к памяти чтобы обнулить далее чтобы что то записать в ячейку ты гуляешь по указателям, тоже тормоза выдели статический массив всего то 10000 ячеек (при инте 40000 байт памяти) а чтобы его не обнулять сделай или глобальным или static скорость возрастет Добавлено через 7 минут ты считаешь закрашенные а потом вычитаешь из общего тут тормоза *if(canvas[i][j] == 1) зачем??? закрашенные 1 не закрашенные 0 т.е прибавишь незакрашенную ячейку результат не изменится
примерно так
1
|
||||||||||||
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
| 01.11.2013, 21:34 [ТС] | |
|
Спасибо всем, это просто моя первая задача в таком формате. я бы и не догадался что нужно input.txt и output.txt создавать. да и массив динамический оказывается не нужен, ну дурак на своих ошибках учится. Главное что в основном решалось все правильно при ручных проверках. в общем дурак на своих ошибках учится. И еще в задаче не указано что w меньше или равно 100, вот я и подумал в сторону дин. массивов.
Добавлено через 19 минут Вот как я мог угадать что у переменно w потолок это 100?
0
|
|
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|||||
| 01.11.2013, 21:34 | |||||
|
0
|
|||||
|
Модератор
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
|
|
| 01.11.2013, 21:35 | |
|
0
|
|
|
Форумчанин
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
||
| 01.11.2013, 21:36 | ||
|
0
|
||
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|
| 01.11.2013, 21:43 | |
|
0
|
|
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
| 01.11.2013, 21:59 [ТС] | |
|
Да понял я на счет не меньше одной))))) просто под вечер я уже никакой + болезнь(ангина, температура). Думаю все когда то болеют.
0
|
|
| 01.11.2013, 22:00 | |
|
1
|
|
|
Неэпический
|
||||||
| 02.11.2013, 01:21 | ||||||
|
Экзотика
ВНИМАНИЕ!!! В коде черт глаза сломает!!!
0
|
||||||
| 02.11.2013, 01:21 | |
|
Помогаю со студенческими работами здесь
18
Подсчет времени работы программы Уменьшение времени выполнения цикла Уменьшение времени выполнения кода Уменьшение\Увеличение времени (посфикс,префикс) Уменьшение размера программы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|