0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
||||||
1 | ||||||
Уменьшение времени работы программы01.11.2013, 16:24. Показов 1835. Ответов 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 | 2 | |||||||||||||||
Слишком много циклов. подсчитывать занятые можно и в первом:
А еще (хз, мож тут и не заметно будет) можно развернуть матрицу в массив(т.е. память выделять один раз), и обращаться как [I] a[j] -> a[j*width+i]. Опять же, на таких данных может прироста и не заметишь...хотя по идее при больших размерах массива это будет быстрее(выделение памяти чертовски накладная операция) Ах да, инициализацию можно занести туда:
1
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
01.11.2013, 19:05 [ТС] | 3 |
0
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|||||||||||
01.11.2013, 19:16 | 4 | ||||||||||
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
Добавлено через 57 секунд Ну, это не означает, что время уменьшилось) Погрешность просто... Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
1
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
01.11.2013, 19:34 [ТС] | 6 |
спасибо. Не уверен что там можно создавать файлы, но попробую и отпишусь.
Добавлено через 2 минуты acmp.ru же=) хочу войти в лимит, что бы поумнеть и получить плюсик в карму
0
|
Форумчанин
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
|
01.11.2013, 19:44 | 7 |
vector<char> будет работать быстрее всех его специализаций. Но если честно, не за чем тут усложнять обычный двумерный массив.
Добавлено через 50 секунд
0
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
01.11.2013, 19:48 [ТС] | 8 |
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
01.11.2013, 19:52 | 9 |
а ларчик то просто открывается: в задаче сказано, что данные должны читаться из файла INPUT.txt и записываться в OUTPUT.txt. у вас они читаются из cin, а записываются в cout, а система ищет файл OUTPUT.txt
1
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|||||||||||
01.11.2013, 20:04 | 10 | ||||||||||
Инспектор Котик,
у тебя алгоритм не тот во первых ты выделяешь память при максиме это 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 [ТС] | 11 |
Спасибо всем, это просто моя первая задача в таком формате. я бы и не догадался что нужно input.txt и output.txt создавать. да и массив динамический оказывается не нужен, ну дурак на своих ошибках учится. Главное что в основном решалось все правильно при ручных проверках. в общем дурак на своих ошибках учится. И еще в задаче не указано что w меньше или равно 100, вот я и подумал в сторону дин. массивов.
Добавлено через 19 минут Вот как я мог угадать что у переменно w потолок это 100?
0
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|
01.11.2013, 21:34 | 12 |
Не больше, ты хотел написать?)
0
|
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
|
|
01.11.2013, 21:43 | 15 |
0
|
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
|
|
01.11.2013, 21:59 [ТС] | 16 |
Да понял я на счет не меньше одной))))) просто под вечер я уже никакой + болезнь(ангина, температура). Думаю все когда то болеют.
0
|
ValeryS
|
01.11.2013, 22:00
#17
|
1
|
Неэпический
|
||||||
02.11.2013, 01:21 | 18 | |||||
Экзотика
ВНИМАНИЕ!!! В коде черт глаза сломает!!!
0
|
02.11.2013, 01:21 | |
02.11.2013, 01:21 | |
Помогаю со студенческими работами здесь
18
Уменьшение времени выполнения цикла Уменьшение времени выполнения кода Уменьшение\Увеличение времени (посфикс,префикс) Уменьшение размера программы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |