Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
#1

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

03.10.2013, 18:12. Просмотров 952. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2013, 18:12     Нужно оптимизировать код
Посмотрите здесь:

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

Нужно оптимизировать - C++
Есть задание, есть готовый код. Но он не проходит скоростной режим, нужно оптимизировать, помогите плз) #include &lt;iostream&gt; ...

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

Оптимизировать код - C++
Доброго времени суток, как можно оптимизировать код что бы он быстрее работал ? Дана последовательность из n чисел a1, a2,..., an. C...

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

Исправить и оптимизировать код - C++
нужна помощь по исправлению ошибок Написал программу она работает все отлично но препод сказал что она не очень красивая Помогите...

Помогите оптимизировать код - C++
Здравствуйте! Помогите, пожалуйста, оптимизировать его: main.cpp #include &quot;main.h&quot; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitriy_M
1341 / 1222 / 112
Регистрация: 20.03.2009
Сообщений: 4,393
Записей в блоге: 11
03.10.2013, 18:29     Нужно оптимизировать код #2
Для начала избавиться от
C++
1
vector<int> v(max,0);
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
03.10.2013, 21:45  [ТС]     Нужно оптимизировать код #3
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Для начала избавиться от
C++
1
vector<int> v(max,0);
кстати да))) действительно, натупил)
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
04.10.2013, 22:48  [ТС]     Нужно оптимизировать код #4
лог тестов
Кликните здесь для просмотра всего текста

Тест Статус Время работы Астрономическое время работы Используемая память
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;
}
Kuzia domovenok
04.10.2013, 22:59
  #5

Не по теме:

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

BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
04.10.2013, 23:14  [ТС]     Нужно оптимизировать код #6
спасибо что заметили))
но мне от этого легче не стало)))
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
04.10.2013, 23:15     Нужно оптимизировать код #7
Цитата Сообщение от BabyGluk Посмотреть сообщение
C++
1
2
for(int i = 1; i<=max;i++)
    yes.insert(i);
Зачем использовать std::set для таких операций? Лучше взять std::vector<bool>, он гораздо компактнее будет лежать в памяти.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
04.10.2013, 23:26     Нужно оптимизировать код #8
Цитата Сообщение от kamre Посмотреть сообщение
Зачем использовать std::set для таких операций? Лучше взять std::vector<bool>, он гораздо компактнее будет лежать в памяти.
так set для того и нужен, чтобы операции над множествами выполнять.

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

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

Добавлено через 1 минуту
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Если идут несколько раз подряд NO, то зачем запоминать все эти числа?
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
Dmitriy_M
1341 / 1222 / 112
Регистрация: 20.03.2009
Сообщений: 4,393
Записей в блоге: 11
05.10.2013, 00:20     Нужно оптимизировать код #12
Цитата Сообщение от kamre Посмотреть сообщение
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
Вот именно. Если был хоть один YES, то хранить все эти числа уже не нужно.
mat_for_c
140 / 135 / 29
Регистрация: 26.04.2013
Сообщений: 650
Завершенные тесты: 2
05.10.2013, 00:53     Нужно оптимизировать код #13
Цитата Сообщение от 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;
}
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
05.10.2013, 01:10  [ТС]     Нужно оптимизировать код #14
спасибо))
но все равно
Превышено максимальное время работы 2.076
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 01:16     Нужно оптимизировать код
Еще ссылки по теме:

Помогите оптимизировать код - C++
Помогите пожалуйста разобраться, хотелось бы чтобы это прграммка наконец-то заработала. Задача такая: Одномерный массив целых чисел,...

Как оптимизировать код? - C++
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение, что можно поменять и изменить для...

Оптимизировать и минимализировать код - C++
Cделал легкую прогу. Понимаю логики 0 в коде. Можете помочь оптимизировать код? А заодно и сделать код более минималистичным. #include...

Как оптимизировать код? - C++
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using namespace...

Оптимизировать код оператор switch - C++
Послкажите что нетак после cin&gt;&gt;v содержимое switch не работает void main() { float inches=2.54; float cm; int...


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

Или воспользуйтесь поиском по форуму:
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
05.10.2013, 01:16     Нужно оптимизировать код #15
Цитата Сообщение от 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
и на этом коде очень много времени потеряется.
Yandex
Объявления
05.10.2013, 01:16     Нужно оптимизировать код
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru