Мой вариант разминки для мозгов: оптимизация кода

А что если разбить так:

unsigned long elements_with_stacks[1000][100]; 

То есть тысяча стеков и в каждом стеке по 100 элементов. Это ведь максимально возможное кол-во стеков и значений в них, так?

Как-то так:

#include <cstdio>

unsigned long elements_with_stacks[1000][100];
short tops[1000];

int main()
{
    unsigned long b;
    short a;
    char str[5];
    register int i;
    int n;
    scanf ( "%d", &n );
    for ( i = 0; i < n; i++ )
    {
        scanf ( "%s%d", str, &a );
        switch( str[1] )
        {
            case 'U':
                {
                    scanf ( "%u", &b );
                    elements_with_stacks[ a-1 ][ tops[a-1]++ ] = b;
                };break;
            case 'O':
                {
                    printf ( "%u\n", elements_with_stacks[ a-1 ][ --tops[a-1] ] );
                };break;
            default:
                {
                    return 1;
                };break;    
        }   
    }   
    return 0;
}   

Но почему-то:

1220. Stacks    Visual C++ 2010 Wrong answer    3   0.031   520 КБ

То есть тысяча стеков и в каждом стеке по 100 элементов. Это ведь максимально возможное кол-во стеков и значений в них, так?

Нет, не так. В задаче не оговорено максимальное количество элементов в каждом стеке. Т.е. все 100тыс. элементов могут оказаться в одном стеке.

Раз идей больше нет, тогда тогда лови...

Делаем три массива: первый для хранения 100тыс. чисел unsigned int, второй — для хранения 1000 «указателей» на верхушки стеков, третий — для хранения 100тыс. связей («указателей» на следующий элемент) между элементами стеков. (Здесь слово «указатель» я намеренно взял в кавычки!)

Пакость заключается в том, что если использовать указатели (pointer), то размер третьего массива будет ~800Кб (по 8 байт на указатель). Если использовать целочисленные индексы по первому массиву, то в сумме первый и третий массивы дадут 400Кб + 400Кб = 800Кб, что тоже много.

Обойти это можно следующим образом.

Идея

1. Для хранения номера (индекса) следующего элемента стека необходимо 17 бит (2^17 = 131072 > 100000). Т.е. тип short мал.
2. Числа, которые необходимо хранить в стеках, не более 10^9 (по условию задачи). Для хранения такого числа достаточно 30 бит. Т.е. имеется 2 неиспользуемых бита.

Из (1) и (2) следует, что для третьего массива можно использовать тип unsigned short, а недостающий бит хранить там же, где и число. Оставшийся 1 бит можно использовать как флаг того, что ячейка занята/свободна.

По памяти получается 400Кб (массив с числами) + 200Кб (массив индексов) + 4Кб (массив индексов верхних элементов стеков) = ~604Кб. Проходим.

Реализация PUSH

1. Функция, реализующая PUSH, получает номер стека и число, которое нужно поместить в стек (данные).
2. Ищем свободную ячейку по массиву данных (это, см. выше, первый массив), используя флаг занятой ячейки.
3. Из массива индексов верхних элементов стеков (второй массив) берётся индекс верхнего элемента для этого стека.
4. В свободную ячейку массива данных заносится число, в 30 младших разрядах которого хранятся данные, бит 30 = 1 — устанавливаем флаг, что ячейка занята, в бит 31 помещаем старший разряд индекса предыдущего элемента стека, полученный на шаге 3.
5. В ячейку массива индексов (ячейка с тем же индексом, что и для массива данных) заносятся 16 младших битов индекса предыдущего элемента стека, полученный на шаге 3.
6. В массив индексов верхних элементов стеков для этого стека заносится индекс добавляемого элемента, полученный на шаге 2.

Реализация POP

1. Функция, реализующая POP, получает номер стека, из которого извлекаются данные, и возвращает это число в качестве результата.
2. Из массива индексов верхних элементов стеков берётся индекс верхнего элемента для этого стека.
3. Из массива данных и массива индексов по индексу, полученному на шаге 2, извлекается информация и формируются «чистые» данные и «чистый» индекс предыдущего элемента стека.
4. В ячейке массива данных (по индексу из шага 2) сбрасывается флаг занятости ячейки.
5. В массив индексов верхних элементов стеков для этого стека заносится индекс предыдущего элемента, полученный на шаге 3.

В общем, всё достаточно элементарно для реализации. Единственно, что здесь я обошёл вниманием — это алгоритм поиска свободной ячейки в массиве данных, Поскольку тупой линейный поиск приводит к Time limit exceeded. Потребуется некая оптимизация поиска. Но это уже достаточно просто ;-)

Реализовывать это всё можно как в виде отдельных функций, так и в виде класса (C или C++). Разницы большой нет. Просто в первом случае функции будут пользоваться глобальными переменными/массивами, а во втором — членами класса.

Поскольку тупой линейный поиск приводит к Time limit exceeded. Потребуется некая оптимизация поиска. Но это уже достаточно просто ;-)

Вот код:

#include <cstdio>

#define size 100000

unsigned long values[size]; //значения
unsigned long tops[1000]; //верхушки стеков
unsigned short pointers[size]; //"указатели" на предыдущщий элемент

void PUSH ( short, unsigned long );
unsigned long POP ( short );

inline int g_bit( unsigned long val, int pos )
{
    return val &= ( 1 << pos );
}

void s_bit( unsigned long&, int, int );

int main()
{
    int n;
    register int i;
    unsigned long b;
    short a;
    char str[5];
    scanf ( "%d", &n );
    for ( i = 0; i < n; i++ )
    {
        scanf ( "%s%d", str, &a );
        switch ( str[1] )
        {
            case 'U':
                {
                    scanf ( "%u", &b );
                    PUSH ( a-1, b );                    
                };break;
            case 'O':
                {
                    printf ( "%u\n", POP ( a-1 ) );
                };break;
            default:
                {
                    return 1;
                };break;
        }
    }
    return 0;
}

void PUSH ( short stack, unsigned long value )
{
    register unsigned long j;
    //ищем свободную ячейку
    for ( j = 0; j < size; j++ )
    {
        if ( !g_bit( values[j], 30 ) )
           break;   //в j - свободная ячейка 
    }
    //на всякий случай :)
    values[j] = 0;
    //В свободную ячейку массива данных заносится число
    values[j] = value; 
    //устанавливаем флаг, что ячейка занята
    s_bit( values[j], 30, 1 );
    //в бит 31 помещаем старший разряд индекса предыдущего элемента стека, полученный на шаге 3.
    if ( g_bit( tops[stack], 17 ) )
        s_bit( values[j], 31, 1 );
    /*В ячейку массива индексов 
     заносятся 16 младших битов индекса предыдущего элемента стека, полученный на шаге 3.*/
    pointers[j] = tops[stack];
    /*В массив индексов верхних элементов стеков для этого стека заносится
    индекс добавляемого элемента, полученный на шаге 2.*/
    tops[stack] = j;
    return;
}

unsigned long POP ( short stack )
{
    register int i;
    unsigned long clear_data, clear_index;
    clear_data = clear_index = 0;
    /*Из массива данных и массива индексов по индексу, полученному на шаге 2, 
    извлекается информация и формируются "чистые" данные и "чистый" индекс предыдущего элемента стека.*/
    for ( i = 0; i < 30; i++ )
        clear_data += g_bit( values[tops[stack]], i );
    clear_index += pointers[tops[stack]];
    clear_index += g_bit( values[tops[stack]], 31 );
    //В ячейке массива данных (по индексу из шага 2) сбрасывается флаг занятости ячейки.
    s_bit( values[tops[stack]], 30, 0 );
    /*В массив индексов верхних элементов стеков для этого стека 
    заносится индекс предыдущего элемента, полученный на шаге 3.*/
    tops[stack] = clear_index;
    return clear_data;  
}

void s_bit( unsigned long &val, int pos, int status )
{
    if ( status )
        val |= ( 1 << pos );
    else
    {
        unsigned long temp = 0;
        for ( int i = 0; i < sizeof( unsigned long ) * 8; i++ )
        {
            if ( g_bit( val, i ) && i != pos )
               temp |= ( 1 << i );
        }
        val = temp;
    }
    return;
}

Вердикт:

1220. Stacks    Visual C++ 2010 Time limit exceeded 10  0.531   368 КБ

Всё дело, наверное, в алгоритме поиска. Но как искать, если ни линейный, ни двоичный, ни интерполяционный поиски не подходят?

Вердикт: тяжелый случай незнания работы с Битовыми операциями.

Сброс двух старших битов в 32-бинтом числе:

val &= 0x3fffffff;

Сброс 30-го бита:

val &= ~0x40000000;

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

Вот исправленный вариант:

void PUSH ( short stack, unsigned long value )
{
    register unsigned long j;
    for ( j = 0; j < size; j++ )
    {
        if ( !( values[j] & 0x40000000 ) )
           break;   
    }
    values[j] = 0;
    values[j] = value; 
    values[j] |= 0x40000000;
    if ( tops[stack] & 0x20000 )
        values[j] |= 0x80000000;
    pointers[j] = tops[stack];
    tops[stack] = j;
    return;
}

unsigned long POP ( short stack )
{
    register int i;
    unsigned long clear_data, clear_index;
    clear_data = clear_index = 0;
    clear_data = 0x3fffffff & values[tops[stack]];
    clear_index += pointers[tops[stack]];
    clear_index += ( values[tops[stack]] & 0x80000000 );
    values[tops[stack]] &= ~40000000;
    tops[stack] = clear_index;
    return clear_data;  
}

Результат тот-же.

P.S.: комментарии в коде почему-то показываются кракозябрами(

Ляпа: if ( tops[stack] & 0x20000 ) 0x20000 — это 18-й бит, а тебе нужен 17-й.

Ещё есть пара лишних присваиваний.

Ну и поиск свободной ячейки «в лоб». Я же сразу сказал, что не прокатит.

По поиску, как вариант: завести еще одну индексную переменную, которая бы отслеживала первую незанятую ячейку. При освобождении ячейки (POP) эту переменную настраивать на эту ячейку. При заполнении ячейки (PUSH) искать следующую незанятую ячейку от текущего положения этого индексного указателя.

Можно сделать две индексных переменных: одна отслеживает оставшееся свободное пространство, а вторая отслеживает освободившиеся ячейки и первыми заполняются именно эти ячейки.

Можно сделать и что-то более «интеллектуальное», но я боюсь, что оно будет относительно медленно работать.

0x20000 — это 18-й бит, а тебе нужен 17-й.

Но...

завести еще одну индексную переменную, которая бы отслеживала первую незанятую ячейку

Как-то так?

#include <cstdio>

#define size 100000

unsigned long values[size];
unsigned long tops[1000]; 
unsigned short pointers[size]; 
unsigned long last_index = 0;

.........

void PUSH ( short stack, unsigned long value )
{
    register unsigned long j;
    for ( j = last_index; j < size; j++ )
    {
        if ( !( values[j] & 0x40000000 ) )
           break;
    }
    values[j] = 0;
    values[j] = value; 
    values[j] |= 0x40000000;
    if ( tops[stack] & 0x20000 )
        values[j] |= 0x80000000;
    pointers[j] = tops[stack];
    tops[stack] = j;
    return;
}

unsigned long POP ( short stack )
{
    register int i;
    unsigned long clear_data, clear_index;
    clear_data = clear_index = 0;
    clear_data = 0x3fffffff & values[tops[stack]];
    clear_index += pointers[tops[stack]];
    clear_index += ( values[tops[stack]] & 0x80000000 );
    values[tops[stack]] &= ~40000000;
    last_index = tops[stack];
    tops[stack] = clear_index;
    return clear_data;  
}

porshe, тут как бы путаница в сколько бит и номер бита, если считать от 0. Для представления 100000 нужно 17 бит, т.е. логично сказать, что старший бит 17-й. Но если считать от 0, то он 16-й. Мог бы и сам посчитать ;-)

Мой вариант решения задачи 1220 Stacks

#include <stdio.h>

using namespace std;

const unsigned int POOLSIZE     = 100001;
const unsigned int STACKQTY     = 1000;

const unsigned int INDEXMASK    = 0x80000000;
const unsigned int BUSYFLAG     = 0x40000000;
const unsigned int DATAMASK     = 0x3fffffff;
const unsigned int LASTFLAG     = 0x1ffff;

class Pool {
    unsigned int datas[POOLSIZE];
    unsigned short indexes[POOLSIZE];
    unsigned int tops[STACKQTY];
    unsigned int free;
public:
    Pool();
    void push(unsigned short stacknum, unsigned int data);
    unsigned int pop(unsigned short stacknum);
};

Pool::Pool() {
    for (unsigned short i = 0; i < STACKQTY; ++i) {
        tops[i] = LASTFLAG;
    }
    for (unsigned int j = 0; j < POOLSIZE; ++j) {
        datas[j] = 0;
    }
    free = 0;
}

void Pool::push(unsigned short stacknum, unsigned int data) {
    unsigned int prev_addr;
    unsigned int addr;
    if (free >= POOLSIZE) {
        for (addr = 0; addr < POOLSIZE; ++addr) {
            if ((datas[addr] & BUSYFLAG) == 0) {
                break;
            }
        }
    }
    else {
        addr = free;
    }
    prev_addr = tops[stacknum];
    tops[stacknum] = addr;
    datas[addr] = data | BUSYFLAG | ((prev_addr & 0x00010000) << 15);
    indexes[addr] = prev_addr & 0xffff;

    unsigned int f_addr;
    for (f_addr = addr+1; f_addr < POOLSIZE && (datas[f_addr] & BUSYFLAG) != 0; f_addr++)
        ;
    if (f_addr >= POOLSIZE) {
        free = LASTFLAG;
    }
    else {
        free = f_addr;
    }
}

unsigned int Pool::pop(unsigned short stacknum) {
    int top = tops[stacknum];
    unsigned int data = datas[top] & DATAMASK;
    unsigned int prev_addr = (((unsigned int)indexes[top]) & 0xffff) | ((datas[top] & INDEXMASK) >> 15);
    datas[top] &= ~BUSYFLAG;
    free = top;
    tops[stacknum] = prev_addr;
    return data;
}


Pool stacks;

int main() {

#ifndef ONLINE_JUDGE
   freopen("data1.txt", "rt", stdin);
   //freopen("output.txt", "wt", stdout);
#endif

    int num_cmd;
    scanf("%u", &num_cmd);

    char cmd[5];
    unsigned int stacknum, value;

    for (int i = 0; i < num_cmd; i++) {

        scanf("%s %u", cmd, &stacknum);

        if (cmd[1] == 'O') {
            // pop
            printf("%u\n", stacks.pop(stacknum-1));
        }
        else {
            // push
            scanf("%u", &value);
            stacks.push(stacknum-1, value);
        }

    }
    return 0;

}

Есть не очень аккуратные фрагменты... однако работает ))

Тот момент, когда понимаешь, что ты и твой код полное г..вно. :(
Спасибо Череп, selevit, было интересно!

Ну, я бы не стал выставлять оценки столь категорично. Твой последний вариант кода практически повторяет мой код, за исключением фрагментов, отвечающих за поиск свободной ячейки. И написал ты его сам. Остальные отличия больше косметические. Этот, первый вариант, я написал на C++ с классами. Второй вариант я переписал на C для того, что бы посмотреть будет ли отличие на Timus'е в результатах. Второй вариант ещё больше похож на твой код. Так что, всё нормально. А если учесть некую объективную разницу в опыте... Я скажу так, что в 8 классе я программы на C++ не писал ))

Чем больше будешь писать программ, тем лучше будет код. И ещё учитывай, что спортивное программирование — это достаточно своеобразная область. Пиши больше, читай книги по алгоритмам, методике программирования — и всё получится. Но практика — это главное.