Быстрый стек, с малым обьемом памяти

@outoftime · Регистрация: 25.07.2009

Студворк — интернет-сервис помощи студентам

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
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
 
#define FOR(i,a,b) for (int i(a), _b(b); i < _b; ++i)
#define ABS(a) ( (a) < 0 ? -(a) : a )
 
using namespace std;
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    cin >> n;
    stack a[1000];
    while (n--)
    {
        int d;
        string s;
        cin >> s >> d;
        if (s == "PUSH")
        {
            int dd;
            cin >> dd;
            a[d-1].push(dd);
        }
        else
            cout << a[d-1].pop() << endl;
    }
    return 0;
}

http://acm.timus.ru/problem.aspx?space=1&num=1220
нужно за 1 секунду и 0,75Мб памяти обработать 0 < N ≤ 100000 запросов к 1 ≤ A ≤ 1000 разным стекам, гарантируется что все запросы коректны, т.е. вывод елемента со стека не может быть раньше чем ввод.
Вроде написал, но компилятор упорно говорит что cannot convert parameter 1 from 'int' to 'void *', как видно a = (int *) realloc(--sz, sizeof(int)); я (int *) дописал, т.е. все верно, может я чего-то непонял, в чем ошибка, подскажите пожалуйста..

Добавлено через 3 минуты
немного доработал ввод, на сишный, т.к. он быстрее, но ошибка с выделением памяти осталась, вот

код

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
#include <iostream>
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char* s;
        scanf("%s",&s);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else
            printf("%d",a[d-1].pop());
    }
    return 0;
}

@odip · 10.01.2010, 21:24

C
1
2
3
4
5
6
struct block_t;
struct block_t {
    int value[MAX_BLOCK_SIZE];
    struct block_t *prev_blk;
};
typedef struct block_t block_t;

@outoftime · 10.01.2010, 21:47 **[ТС]**

int value[MAX_BLOCK_SIZE];
я запутался, а где тогда выделять malloc-ом память? или здесь надо просто указатель которому выделяем память?

@odip · 10.01.2010, 21:52

в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );

@outoftime · 10.01.2010, 22:02 **[ТС]**

Сообщение от odip

в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );

извените коль что просто я и си++ не очень хорошо знаю, а чистый си вообще.. и кажется где-то читал что определять размер струкруры нельзя

Добавлено через 1 минуту

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
#include <stdio.h>
 
struct block_t;
struct block_t
{
    int val[19];
    struct block_t* prev;
};
 
typedef struct block_t block_t;
 
struct stack
{
    block_t* inf;
    int top;
    stack()
    {
        inf->prev = 0;
        top = 0;
    }
    ~stack(){}
    void push(int &n)
    {
        if (top == 19)
        {
            top = 0;
            block_t* tmp = malloc(sizeof(block_k));
        }
        else
        {
            inf->val[top++] = n;
        }
    }
};
 
int main()
{    
    return 0;
}

Добавлено через 11 секунд
куча ошибок:

Добавлено через 1 минуту
16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before "stack"

16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] no semicolon at end of struct or union
19 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] data definition has no type or storage class
20 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token
22 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '&' token

C:\Documents and Settings\Администратор\Рабочий стол\timus.c In function `push':

27 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `block_k' undeclared (first use in this function)
(Each undeclared identifier is reported only once for each function it appears in.)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `inf' undeclared (first use in this function)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `n' undeclared (first use in this function)
At top level:
34 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token

@GRANDEATH · 10.01.2010, 22:20

У меня другое решение. Я создаю массив определенного размера и массив дескрипторов на него. То есть грубо говоря - разбиваю массив на страницы (извиняюсь, за неправильный термин, но не знаю, как ещё можно сказать). Отдельно есть массив char, содержащий 0 - если данный блок свободен, 1 - если занят. Я думаю, что сдесь лучше сего было использовать биты, а не байты, то было бы лучше. Если объясните, как делать тоже самое, только с битами, скажу СПАСИБО.
Тут два класса Memory - описывающий функции allocate_block free_block - выделяющий память и помечающий блок, как свободный. Реализация стека через выделяемые блоки памяти.
Писал на С++, поэтому накладных расходов много.
Вот код. Извиняюсь за неструктурированнось, так классы были разбиты по файлам, которые я инклюдил.

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// Task_2.cpp : Defines the entry point for the console application.
#include <stdio.h>
//#include <malloc.h>
 
 
 
#define BLOCK_SIZE 40
#define ARRAY_SIZE 400000
#define NUMBER_OF_POINTERS 10000 // = ARRAY_SIZE / BLOCK_SIZE
 
 
 
class Memory
{
public:
    //set_free();
    int* allocate_block(); //?????? ??????
    void free_block(int *p); // ???????? ??????
    Memory(void);
    ~Memory(void);
    void print(int a,int b);
 
private:
    int* data;
    char* indexes;
};
 
 
 
struct Descriptor
{
    int* position; //??????? ? ???? ????????
    Descriptor *next; //????????? ??????????
};
 
 
 
 
class stack
{
public:
    stack(void);
    ~stack(void);
    void push(int i);
    int pop();
    int debug_info_pos(); 
private:
    Descriptor root; //?????? ??????
    int pos; //?????? ???????
    int* local_pointer; // ????????? ?? ??????? ????. ???????? ????????.
};
 
 
int main()
{
 
        
        int n;
        scanf("%d",&n);
        stack *a = new stack[1000];
  
        char* temp = new char[20]; // 
        while (n--)
        {
                int d;
                scanf("%s",temp);
                //cin >> temp;
                scanf("%d",&d);
                //cin >> d;
                if (temp[1] == 'U') //
                {
                        int dd;
                        //cout << dd;
                        scanf("%d",&dd);
                        //cin >> dd;
                        a[d-1].push(dd);
                }
                else
                        //cout << a[d-1].pop() << endl;
                        printf("%d\n",a[d-1].pop());
        }
        
    
    //system("pause");
    
    return 0;
}
 
 
Memory my_memory;
 
stack::stack(void)
{
    local_pointer = root.position = my_memory.allocate_block(); //Âûäåëèòü áëîê èç "êó÷è"
    root.next = NULL;
    pos = 0;
}
 
 
 
 
void stack::push(int i)
{
    if (pos == BLOCK_SIZE - 1) //Åñëè óæå íåò ïÿìÿòè â ýòîé ñòðàíèöå
    {
        Descriptor *temp = &root;
        while ( temp->next!= NULL)
        {
            temp = temp->next;
        }; //Èùåì â ñïèñêå íóëåâîé óêàçàòåëü
        
        
        temp->next = new Descriptor; // Ñîçäàåì äåñêðèïòîð
        temp->next->position = my_memory.allocate_block();
        local_pointer = temp->next->position;
        temp->next->next = NULL; //Ñëåäóùåãî íåò
        
        pos = 0; // Çàïîëíÿòü áëîê ñ 0-ãî ýëåìåíòà
        
    }
    *(local_pointer + pos) = i; //Çàïèøè òóäà äàííûå
    pos++; //Óâåëè÷ü ïîçèöèþ íà 1
}
 
int stack::pop()
{
    pos--; // Óìåíüøü èíäåêñ
    
    
    if (pos < 0) //Åñëè èíäåêñ ìåíüøå 0. Òî åñòü òåêóùèé áëîê ïóñòîé
    {
        Descriptor *temp = &root;
        if (temp->next != NULL) //Åñëè íå îäèí áëîê
        {   
            while ( temp->next->next!= NULL)
            {
                temp = temp->next;
            }; //Èùåì â ñïèñêå àäðåñ äåñêðèïòîðà, ÷åé ñëåäóþùèé ýëåìåíò ñ íóëåâûì óêàçàòåëåì
            
            my_memory.free_block(temp->next->position); //îñâîáîäèòü ýòîò áëîê
            temp->next = NULL; //Óíè÷òîæèòü áëîê
            local_pointer = temp->position; //Ïðèñâàèâàåì àäðåñ íà âåðõóøêó ñòåêà
            pos = BLOCK_SIZE - 2; // Ïîñëåäíÿÿ ïîçèöèÿ â ýòîì áëîêå
        }
        else throw(1);
        
    }
    //int *p = (local_pointer + pos);
    int res = *(local_pointer + pos); //Èçâëåêè äàííûå
    //cout << "pos = " << pos << " ";
    //if (res == 59) throw(2);
    /*static bool first = true;
    if (first)
    {
        my_memory.print(0,20);
        first = false;
    } */
    return res;
}
 
stack::~stack(void)
{
}
 
int stack::debug_info_pos()
{ 
    return pos;
};
 
Memory::Memory(void)
{
    data = new int[ARRAY_SIZE];
    indexes = new char[NUMBER_OF_POINTERS];
    for (int i = 0; i < NUMBER_OF_POINTERS; i++)
        indexes[i] = 0; //Âñå ñâîáîäíî
}
 
int* Memory::allocate_block()
{
    int i = 0;
    while (i++ < NUMBER_OF_POINTERS)
    {
        if (indexes[i] == 0) //Åñëè ýòîò áëîê ñâîáîäåí
        {
            indexes[i] = 1; //Óñòàíîâèòü ôëàã çàíÿòîñòè
            return &data[BLOCK_SIZE*i]; //Âåðíóòü óêàçàòåëü íà ýòîò áëîê. Äëèííà êàæäîãî áëîêà BLOCK_SIZE
        }
    }
    
    return NULL; //Íåò òàêîé ïàìÿòè
}
 
void Memory::free_block(int* p)
{
    int offset = (p - &data[0])/sizeof(int); //Îïðåäåëè ñìåùåíèå
    indexes[0] = 0; //Óñòàíîâè ôëàã ñâîáîäíîñòè
}
 
Memory::~Memory(void)
{
 
};
/*void Memory::print(int a,int b)
{
    for (int i = a; i < b; i++)
        cout << "memory[" << i << "] = " << data[i] << endl;
    cout << endl;
}*/

Выложил, вдруг кому-то станет интересен принцип.

Добавлено через 33 секунды
Результат:

1220 C++ Accepted 0.078 761 KB

Добавлено через 55 секунд
Извиняюсь за кодировку...

@outoftime · 10.01.2010, 22:41 **[ТС]**

Сообщение от GRANDEATH

как делать тоже самое, только с битами

кажется на си++ есть библиотека для работы с битмасками

Добавлено через 9 минут
подскажите как мне доделать свой вариант? катать ваш пример не хочу, толку будет мало, а так в голове останется..

@GRANDEATH · 10.01.2010, 23:31

Я так понимаю, что ты хочешь сделать через списки.
Тебе потребуется массив из 1000 структур, содержащие
1. Смещение внутри твоего 19-ти элементного блока
2. Указатель на начало списка

Список состоит из структур, котрые, как уже я увидел ты сделал.

Суть в чем - у тебя есть массив из структур, назови его своеобразной кучей
struct data_block
{
int data[19];
data_block *next;
}
и есть массив битов, которые показывают свободен ли этот блок.
1. Запись
Записывай в текущем блоке преременные, пока смещение не будет 18 (счет в си с 0

)
Если блок забит - найди по биту первый свободный блок и пристыкуй его к своему списку.
Установи смещение на 0.
2. Чтение.
Считывай, пока смещение не станет 0.Как только стало нулем отстыкуй блок. Пометь его как свободный (для дальнейшего использования). Установи смещение на 18 (последный элемент).

В целом - это примитивный алгоритм.
Я бы описал основные данные так:
struct data_block
{
int data[19];
data_block *next;
} - твоя единица памяти
data_block array[ Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ];
byte access[Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ]; // Здесь бы использовать битовое поле. Но я его не знаю.

struct stack_begin
{
int offset;
data_block* last; //Это излишне. Для того, что бы каждый раз тебе не пробегать по списку, для нахождения последнего элемента. Быстродействие увечилит в разы, а память сожрет только паку килобайт (ну или десятков)
data_block* first; //Указатель на первый блок
}

Теперь надо будет обьявить пару функций
1. Запихни в стек
2. Вытащи из стека
+ дополнит. функции
1. Верни свободный блок из кучи
2. Возвтрати блок в кучу.
3. Верни адрес предпоследнего блока в списке.
Ты так хотел делать?

@outoftime · 11.01.2010, 09:55 **[ТС]**

GRANDEATH, то как я хотел сделать я сделал, дальше я потерялся, просто у меня выходит, что выделяем мы память сразу всю, и при этом говорим две вещи:
1) каждому непустому стеку как минимум 1 блок
2) в каждом блоке 19 элементов
Вот эти две вещи меня и запутали, т.к. у нас каждый стек, который занимает больше N*19 элементов будет занимать на 18*4 байта больше чем он должен занимать..
Спасибо большое за детально расжеваный алгоритм, и за то что нет ни строчки кода. Попытаюсь как-то закодить..

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set, //масив, для занятых/свободных блоков
       * heap; //блок на все стеки, или просто куча
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top; 
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int)); // вделяем память на "битмаску" и "кучу"
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0); //освобождаем --||--
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find() //ищем и возвращаем указатель на ближайший свободный блок
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n) //определяем блок как свободный
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack() //выделяем память на корень стека
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack() //освобождаем память
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size) //если текущий блок забит ищем новый
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0) //если текущий блок пуст, переходим к предыдущему
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[top--];
}

Есть проблемка: почему-то int stack :: pop() пашет неправельно, он достает элемент перед тем который надо достать

Добавлено через 39 минут
поисправлял ошибки, int stack :: pop() возвращала не предыдущий а следующий, вот верный код:

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
        head->val[top++] = n;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[--top];
}

Добавлено через 3 минуты
С++ Wrong answer 0.015сек 481 КБ

Добавлено через 5 минут
У меня вылетает последний елемент блока

Добавлено через 6 минут
нашел, исправил,

вот

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size;
    }
    return head->val[--top];
}

Добавлено через 1 минуту
Результат проверки № теста Время работы Выделено памяти
Memory limit exceeded 10 0.062 869 КБ

@GRANDEATH · 11.01.2010, 15:41

Memory limit exceeded 10 0.062 869 КБ

Вот оно и гадость( Попробуй выделить не 20, а 40?
+ сотри #icnclude <iostream>
Мало ли что системе в голову взбредет...

@odip · 11.01.2010, 15:45

Memory limit exceeded 10 0.062 869 КБ

Да фигню какую-то в коде написал.
Например зачем вот это:

Memory::Memory()
{
bit_set = (int *) calloc (heap_size, sizeof(int));
heap = (int *) malloc(heap_size * block_size * sizeof(int));
}

@GRANDEATH · 11.01.2010, 15:45

C++
1
2
3
heap = (int *) malloc(heap_size * block_size * sizeof(int));
 
const int heap_size = 60*1000

а это ещё зачем.. Память под 60 * 19*1000 int'ов. Тебе столько не надо...
Тут она отрезает 60 000* 20 (размер блока) * 4 (занимает int) = 60 кб * 20 * 4 это дофига памяти. Что-то она больно мало показала

@outoftime · 11.01.2010, 17:19 **[ТС]**

Сообщение от GRANDEATH

Что-то она больно мало показала

так ведь процес до конца не завершился, они на этапе работы проверяют ограничения

Добавлено через 1 минуту
сколько тогда нужно выделить heap_size и block_size что-бы было норм?

Добавлено через 6 минут
Crash (access violation) 10 0.046 689 КБ
на этом коде:

C++
1
2
const int heap_size = 5*1000,
          block_size = 20;

@odip · 11.01.2010, 18:05

сколько тогда нужно выделить heap_size и block_size что-бы было норм?

Нисколько.
По умолчанию НИЧЕГО не выделено.
Выделение памяти происходит по запросу - как требуется память.

@outoftime · 11.01.2010, 19:29 **[ТС]**

Сообщение от odip

По умолчанию НИЧЕГО не выделено.
Выделение памяти происходит по запросу - как требуется память.

Немного непонял к чему вы, ведь идея состояла в том, что-бы веделить часть памяти целиком, а потом распределять ее внутри програмы..

Добавлено через 4 минуты

Сообщение от odip

Еще вариант - вообще без блоков.
Выделяем 100000*7 байт
4 байта - число
3 байта - ссылка на предыдущий элемент

а как тогда на выделеной памяти созадать ссылки, т.е. присвоить указателю части выделеной памяти я понимаю как, а как указателю присвоить место в памяти, в котором будет хранится его значение?

@odip · 11.01.2010, 19:32

Я уже отказался от этой идеи

Решил выделять блоками.
Прикол в том, что там неизвестно какой компилятор и трудно выделить ровно столько памяти чтобы ее хватило и в тоже время не перебрать.
Выделение делаю malloc(), не использую realloc() и никогда не делаю free().

Добавлено через 45 секунд

а как тогда на выделеной памяти созадать ссылки, т.е. присвоить указателю части выделеной памяти я понимаю как, а как указателю присвоить место в памяти, в котором будет хранится его значение?

Скорее всего ничего не получится - там похоже накладные расходы превышают 50Kb.

Ссылки очень просто - ссылка - это номер в массиве

То есть сразу выделяем 700000 байт одним куском.
Этого точно хватит на задачу.

@outoftime · 11.01.2010, 20:05 **[ТС]**

опять запутался, давайте я скажу на что у меня расходуется память а вы скажете где ее можно укротить?
я выделяю 2 блока, 1-ый для нужд самих стеков, он идет 400 Кб, 2-ой в качестве битмаски, он на 40 Кб
потом при создании стеков, каждые ил элементов имеет два указатели, 1 на значение, и 1 на предыдущий элемент, и того максимум 40 Кб + 4 Кб на текущие размеры стеков
+ 2 инта в мейне и масив 5 чаров, и того = 400+40+40+4+8+20 = 512 Кб

Добавлено через 11 секунд

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 10*1000,
          block_size = 10;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d, dd;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size;
    }
    return head->val[--top];
}

в коде поменял только размер и количество блоков

где еще 300 Кб спрятано?

@Хохол · 22.06.2010, 13:06

Вот читерское решение.

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
#include <fstream>
#include <string>
 
using namespace std;
 
#ifndef ONLINE_JUDGE
ifstream cin("input.txt");
ofstream cout("output.txt");
#else
#include <iostream>
#endif
 
int size[1000] = {0}, n, x, y, *st[1000], ms[1000] = {0};
string str;
 
void prepare()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str >> x;
        x--;
        if(str == "PUSH")
        {
            cin >> y;
            size[x]++;
            ms[x] = max(ms[x],size[x]);
        }
        else
            size[x]--;
    }
    for(int i = 0; i < 1000; i++)
        st[i] = new int[ms[i]];
    for(int i = 0; i < 1000; i++)
        size[i] = 0;
}
 
int main()
{
    prepare();
 
    #ifndef ONLINE_JUDGE
    ifstream cin("input.txt");
#else
    fseek(stdin,0,SEEK_SET);
#endif  
 
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str >> x;
        x--;
        if(str == "PUSH")
        {
            cin >> y;
            st[x][size[x]] = y;
            size[x]++;
        }
        else
        {
            size[x]--;
            cout << st[x][size[x]] << endl;
        }
    }
}

Но нормальное у меня тоже есть.

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №3) Maks 15.11.2026 Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .	Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	10.01.2010, 21:47 [ТС]
	int value[MAX_BLOCK_SIZE]; я запутался, а где тогда выделять malloc-ом память? или здесь надо просто указатель которому выделяем память? 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	10.01.2010, 21:52
	в памяти выделяется одна структура типа block_t block_t *pblk= malloc( sizeof(block_t) ); 1

@GRANDEATH 39 / 39 / 1 Регистрация: 13.09.2009 Сообщений: 108
	10.01.2010, 23:31
	Я так понимаю, что ты хочешь сделать через списки. Тебе потребуется массив из 1000 структур, содержащие 1. Смещение внутри твоего 19-ти элементного блока 2. Указатель на начало списка Список состоит из структур, котрые, как уже я увидел ты сделал. Суть в чем - у тебя есть массив из структур, назови его своеобразной кучей struct data_block { int data[19]; data_block next; } и есть массив битов, которые показывают свободен ли этот блок. 1. Запись Записывай в текущем блоке преременные, пока смещение не будет 18 (счет в си с 0 ) Если блок забит - найди по биту первый свободный блок и пристыкуй его к своему списку. Установи смещение на 0. 2. Чтение. Считывай, пока смещение не станет 0.Как только стало нулем отстыкуй блок. Пометь его как свободный (для дальнейшего использования). Установи смещение на 18 (последный элемент). В целом - это примитивный алгоритм. Я бы описал основные данные так: struct data_block { int data[19]; data_block next; } - твоя единица памяти data_block array[ Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ]; byte access[Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ]; // Здесь бы использовать битовое поле. Но я его не знаю. struct stack_begin { int offset; data_block* last; //Это излишне. Для того, что бы каждый раз тебе не пробегать по списку, для нахождения последнего элемента. Быстродействие увечилит в разы, а память сожрет только паку килобайт (ну или десятков) data_block* first; //Указатель на первый блок } Теперь надо будет обьявить пару функций 1. Запихни в стек 2. Вытащи из стека + дополнит. функции 1. Верни свободный блок из кучи 2. Возвтрати блок в кучу. 3. Верни адрес предпоследнего блока в списке. Ты так хотел делать? 1