Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.78/9: Рейтинг темы: голосов - 9, средняя оценка - 4.78
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167

Нужно оптимизировать код

03.10.2013, 18:12. Показов 1942. Ответов 16
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вобщем код не принемает сайт, немного нагружает и по времени не проходит

задание
Кликните здесь для просмотра всего текста
Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданныъх вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP. Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.


вход
Кликните здесь для просмотра всего текста
10
1 2 3 4 5
YES
2 4 6 8 10
NO
HELP

выход
Кликните здесь для просмотра всего текста
1 3 5


мой код
Кликните здесь для просмотра всего текста
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<set>
#include<string>
#include <sstream>     
#include <algorithm>   
#include<vector>
using namespace std;
int main(int argc, char* argv[])
{
    set<int> main,tmp,yes,no;
    
    int max;
 
    string str;
    cin>>max;
 
    for(int i = 1; i<=max;i++)
        yes.insert(i);
 
    while(str!="HELP"){
        cin>>str;
        istringstream iss (str);
        for(int i = 0;i<str.size();i++)
        {
            int x;
            iss>>x;
            if (x <= max)
                tmp.insert(x);
        }
        if (str == "YES")
        {
            vector<int> v(max,0);  
        vector<int>::iterator it;
        it = set_intersection(yes.begin(),yes.end(), tmp.begin(), tmp.end(), v.begin());
    v.resize(it-v.begin());
 
    
            yes.clear();
            for(it = v.begin();it != v.end();it++)
                yes.insert(*it);
            tmp.clear();
        }
        if (str =="NO"){
             
            vector<int> v(max,0);  
        vector<int>::iterator it;
        it = set_union(no.begin(),no.end(), tmp.begin(), tmp.end(), v.begin());
    v.resize(it-v.begin());
 
    
            no.clear();
            for(it = v.begin();it != v.end();it++)
                no.insert(*it);
            tmp.clear();
        }
 
        
    
    }
 vector<int> v(max,0);  
  std::vector<int>::iterator it;
    it = set_difference (yes.begin(),yes.end(), no.begin(), no.end(), v.begin());
    v.resize(it-v.begin());
    for(it = v.begin();it != v.end();it++)
        cout<<*it<<" ";
        cout<<endl;
 
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.10.2013, 18:12
Ответы с готовыми решениями:

Нужно оптимизировать код
Нужно максимально сократить код #include &lt;iostream&gt; using namespace std; int main(int argc, char** argv) { int a, i,...

Нужно оптимизировать код
Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии....

Нужно оптимизировать готовый код, чтобы не было стыдно показать
Мне дали сделать задачку, чтобы проверить мои знания в ООП (я только 2 месяца назад начал изучать С++). И так, задача: Я написал...

16
1443 / 1326 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
03.10.2013, 18:29
Для начала избавиться от
C++
1
vector<int> v(max,0);
1
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
03.10.2013, 21:45  [ТС]
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Для начала избавиться от
C++
1
vector<int> v(max,0);
кстати да))) действительно, натупил)
0
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
04.10.2013, 22:48  [ТС]
лог тестов
Кликните здесь для просмотра всего текста

Тест Статус Время работы Астрономическое время работы Используемая память
1 OK 0.004 0.004 1339392
2 OK 0.004 0.004 1339392
3 OK 0 0.004 1339392
4 OK 0.008 0.009 1339392
5 OK 0.008 0.008 1339392
6 OK 0.08 0.084 2830336
7 OK 1.032 1.032 14532608
8 OK 0.396 0.397 1613824
9 Превышено максимальное время работы 2.068 2.076 6615040


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<set>
#include<string>
#include <sstream>     
#include <algorithm>   
#include<vector>
#include <iterator>
using namespace std;
 
 
int main(int argc, char* argv[])
{
    set<int> result,tmp,yes,no;
    set<int>::iterator it;
    int max;
    int word;
    int x;
    string str;
    cin>>max;
 
    for(int i = 1; i<=max;i++)
        yes.insert(i);
 
    while(str!="HELP"){
    getline (cin,str);
    stringstream ss;
    ss.str(str);
    while(ss>>word) tmp.insert(word);
        if (str == "YES")
        {
            set_intersection(yes.begin(),yes.end(),tmp.begin(),tmp.end(),inserter(result,result.end()));
            yes.clear();
            yes.insert(result.begin(),result.end());
            tmp.clear();
            result.clear();
        }
        if (str =="NO"){
            set_union(no.begin(),no.end(),tmp.begin(),tmp.end(),inserter(result,result.end()));
            no.clear();
            no.insert(result.begin(),result.end());
            tmp.clear();
            result.clear();
        }
 
 
    }
        set_difference(yes.begin(), yes.end(), no.begin(), no.end(),inserter(result, result.end()));
            ostream_iterator<int> out_it (cout," ");
            copy ( result.begin(), result.end(), out_it );
    return 0;
}
0
04.10.2013, 22:59

Не по теме:

Цитата Сообщение от BabyGluk Посмотреть сообщение
Вобщем код не принемает сайт
В общем, код не принимает сайт.

1
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
04.10.2013, 23:14  [ТС]
спасибо что заметили))
но мне от этого легче не стало)))
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
04.10.2013, 23:15
Цитата Сообщение от BabyGluk Посмотреть сообщение
C++
1
2
for(int i = 1; i<=max;i++)
    yes.insert(i);
Зачем использовать std::set для таких операций? Лучше взять std::vector<bool>, он гораздо компактнее будет лежать в памяти.
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
04.10.2013, 23:26
Цитата Сообщение от kamre Посмотреть сообщение
Зачем использовать std::set для таких операций? Лучше взять std::vector<bool>, он гораздо компактнее будет лежать в памяти.
так set для того и нужен, чтобы операции над множествами выполнять.

Кстати, при чём тут vector<bool> ??? Как он поможет в этой задаче?
0
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
04.10.2013, 23:41  [ТС]
когда команда YES
мне нужно сделать пересечение строки и сета yes.
когда NO тогда нужно обьеденить строку и ноу..
а когда хелп то получить разницу(ес,ноу)

Добавлено через 9 минут
Работает то все как нужно, только последний тест очень грузит..
может есть другие методы для работы с множествами?
0
1443 / 1326 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
04.10.2013, 23:59
BabyGluk, а дальше нужно менять алгоритм.
Для чего этот код?
C++
1
2
for (int i = 1; i <= max; i++)
        yes.insert(i);
Если идут несколько раз подряд NO, то зачем запоминать все эти числа?
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
05.10.2013, 00:05
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Кстати, при чём тут vector<bool> ??? Как он поможет в этой задаче?
В этой задаче, действительно, ни при чем. Просто автор изначально не верно подошел к решению, не должно быть никаких O(n) операций без необходимости, т.к. n может быть огромным, а количество чисел во входном файле очень небольшое. Лучше для всех YES отдельно делать пересечения и для всех NO - объединение, и при выводе проверять вхождения элементов.

Добавлено через 1 минуту
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Если идут несколько раз подряд NO, то зачем запоминать все эти числа?
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
1
1443 / 1326 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
05.10.2013, 00:20
Цитата Сообщение от kamre Посмотреть сообщение
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
Вот именно. Если был хоть один YES, то хранить все эти числа уже не нужно.
1
 Аватар для mat_for_c
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
05.10.2013, 00:53
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Если был хоть один YES,
а зачем выводить те числа, которые встретятся в NO??

Добавлено через 27 минут
BabyGluk, попробуйте так:
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
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<set>
#include<string>
#include <sstream>     
#include <algorithm>   
#include <iterator>
using namespace std;
 
int main(int argc, char* argv[])
{
  set<int> result,tmp,yes,no;
  int max, word;
  string str;
    
  cin>>max;
 
  for(int i = 1; i<=max;i++)
    yes.insert(i);
 
  while(str!="HELP"){
    getline (cin,str);
    stringstream ss;
    ss.str(str);
    while(ss>>word) tmp.insert(word);
    if (str == "YES") {
      set_intersection(yes.begin(),yes.end(),tmp.begin(),tmp.end(),inserter(result,result.begin()));
      yes.swap(result);
      result.clear();
      tmp.clear();
    }
    if (str =="NO") {
      set_union(no.begin(),no.end(),tmp.begin(),tmp.end(),inserter(result,result.begin()));
      no.swap(result);
      result.clear();
      tmp.clear();
    }
  }
  set_difference(yes.begin(), yes.end(), no.begin(), no.end(), inserter(result,result.begin()));
  ostream_iterator<int> out_it (cout," ");
  copy ( result.begin(), result.end(), out_it );
  return 0;
}
1
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
05.10.2013, 01:10  [ТС]
спасибо))
но все равно
Превышено максимальное время работы 2.076
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
05.10.2013, 01:16
Цитата Сообщение от mat_for_c Посмотреть сообщение
C++
1
2
for(int i = 1; i<=max;i++)
yes.insert(i);
Нельзя же так делать. Будет на входе что-то вроде:
100000000
1 2 3 4 5
YES
2 4 6 8 10
NO
HELP
и на этом коде очень много времени потеряется.
1
26 / 26 / 3
Регистрация: 10.04.2013
Сообщений: 167
05.10.2013, 01:31  [ТС]
kamre, понял о чём вы)
но только если не заполнить его от 1 до макс, то в логах все тесты фейл, и всеравно последний "время".. =(
0
1443 / 1326 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
05.10.2013, 15:22
Цитата Сообщение от mat_for_c Посмотреть сообщение
а зачем выводить те числа, которые встретятся в NO??
В случае когда идет несколько раундов YES, NO, то из множества YES делаешь вычитания текущего множества NO.
Дальше NO тебе не нужен.
Цитата Сообщение от BabyGluk Посмотреть сообщение
но только если не заполнить его от 1 до макс, то в логах все тесты фейл, и всеравно последний "время".. =(

Начни думать, а не тупа печатать STL алгоритмы. Распространенная реализация std::set это дерево, конструирование дерева, обход дерева это оверхед. Если входные данные всегда упорядоченны и не содержат повторяющихся элементов, то реализация на упорядоченных списках будет побыстрее работать.

У тебя два множества yes и no, различные ситуации можно определить по состоянию yes и no.
Если ничего не забыл, то будет как то так
Кликните здесь для просмотра всего текста

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
 
int main(int argc, char* argv[])
{
    set<int> yes, no;
    int max;
    string str;
    cin >> max;
 
    while (str != "HELP")
    {
        getline(cin, str);
        stringstream ss;
        ss.str(str);
        set<int> input;
        int word;
        while (ss >> word)
        {
            input.insert(word);
        }
        if (str == "YES")
        {
            if(yes.empty())
            {
                // не разу не был YES
                yes = input;
                if(!no.empty())
                {
                    //вычитаем множество no из yes
                    std::set<int> result;
                    set_difference(yes.begin(), yes.end(), no.begin(), no.end(),
                            inserter(result, result.end()));
                    yes = result;
                    no.clear();
                }
            }
            else
            {
                // второй и более YES
                std::set<int> result;
                set_intersection(yes.begin(), yes.end(), input.begin(), input.end(),
                        inserter(result, result.end()));
                yes = result;
            }
        }
        if (str == "NO")
        {
            if(yes.empty())
            {
                // не было ни одного YES
                // накапливаем NO
                no.insert (input.begin (), input.end());
            }
            else
            {
                //вычитаем входное множество из yes
                std::set<int> result;
                set_difference(yes.begin(), yes.end(), input.begin(), input.end(),
                        inserter(result, result.end()));
                yes = result;
            }
        }
    }
 
    if(yes.empty() && !no.empty())
    {
        // не было ни одного YES
        // выводим разность [1..n] и no
        typedef set<int>::const_iterator Iterator;
        Iterator noItr(no.begin());
        Iterator endItr(no.end());
        for(int i = 1; i < max; ++i)
        {
            if(noItr != endItr)
            {
                if(i<*noItr)
                {
                    std::cout<<i;
                }
                else
                {
                    // i есть в NO
                    // пропускаем
                    ++noItr;
                }
 
            }
            else
            {
                cout<<i<<" ";
            }
 
        }
    }
    if(!yes.empty() && no.empty())
    {
        // ответ в yes.
        //...
    }
    if(yes.empty() && no.empty())
    {
        // вырожденный случай
        // не было ни YES, ни NO, а сразу HELP
        for(int i = 1; i< max; ++i)
        {
            cout<<i<<" ";
        }
 
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
05.10.2013, 15:22
Помогаю со студенческими работами здесь

Нужно оптимизировать
Есть задание, есть готовый код. Но он не проходит скоростной режим, нужно оптимизировать, помогите плз) #include...

Змейка. Нужно оптимизировать
Написал игру &quot;Змейка&quot;,вернее скоро напишу. Вся проблема в том,что я не могу ее нормально оптимизировать. #include &quot;pch.h&quot; ...

Нужно оптимизировать функцию
Немножко не шарю но она должна сортировать пузырьком: #include &lt;iostream&gt; #include &lt;time.h&gt; using namespace std; int...

Оптимизировать код
Для решения задачи : &quot;Note: Write a solution that only iterates over the string once and uses O(1) additional memory, since this is what...

Оптимизировать код
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар чисел, для которых выполняется nums...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Первый деплой
lagorue 16.01.2026
Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru