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

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

Восстановить пароль Регистрация
 
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
03.10.2013, 18:12     Нужно оптимизировать код #1
Вобщем код не принемает сайт, немного нагружает и по времени не проходит

задание
Кликните здесь для просмотра всего текста
Август и Беатриса играют в игру. Август загадал натуральное число от 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 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
Сообщений: 438
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
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 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
Сообщений: 438
05.10.2013, 00:05     Нужно оптимизировать код #11
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Кстати, при чём тут vector<bool> ??? Как он поможет в этой задаче?
В этой задаче, действительно, ни при чем. Просто автор изначально не верно подошел к решению, не должно быть никаких O(n) операций без необходимости, т.к. n может быть огромным, а количество чисел во входном файле очень небольшое. Лучше для всех YES отдельно делать пересечения и для всех NO - объединение, и при выводе проверять вхождения элементов.

Добавлено через 1 минуту
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Если идут несколько раз подряд NO, то зачем запоминать все эти числа?
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
05.10.2013, 00:20     Нужно оптимизировать код #12
Цитата Сообщение от kamre Посмотреть сообщение
Например, чтобы вывести оставшиеся числа из [1, n], если YES вообще не было.
Вот именно. Если был хоть один YES, то хранить все эти числа уже не нужно.
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 584
Завершенные тесты: 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
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
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
и на этом коде очень много времени потеряется.
BabyGluk
26 / 26 / 4
Регистрация: 10.04.2013
Сообщений: 167
05.10.2013, 01:31  [ТС]     Нужно оптимизировать код #16
kamre, понял о чём вы)
но только если не заполнить его от 1 до макс, то в логах все тесты фейл, и всеравно последний "время".. =(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 15:22     Нужно оптимизировать код
Еще ссылки по теме:

C++ Как оптимизировать код?
C++ Оптимизировать код
C++ Оптимизировать и минимализировать код

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

Или воспользуйтесь поиском по форуму:
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
05.10.2013, 15:22     Нужно оптимизировать код #17
Цитата Сообщение от 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;
}
Yandex
Объявления
05.10.2013, 15:22     Нужно оптимизировать код
Ответ Создать тему
Опции темы

Текущее время: 08:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru