I created every stack using pointers, but nodes in this stack saved data of ten last pushed elements, not of one last. So this is a stack of arrays and not the stack of single elements. Also I had an additional array of int[1000], that showed how many positions in last node of each stack is already used.

Conclusion: you need to do such a struct of that has an array of ten elements and a pointer to previous node. On every push-call you should create another node(if previous is full) and add an element on the first open space of node, then increase the number of used positions. On every pop-call you should go to previous node and delete current node(if current node is empty) and print the last element of node, then decrease the number of used positions.

Hope it'll help you. And I apologize for my poor english)

Earlier this problem has got a strict result about a lot of realizations - about two years ago I have a submit which got a MLE 10 (7603331), but now this code on same compiler (VS C++ 2017) have only 252 KB! But on G++ - MLE 1. Similarly - my older AC code now have less memory.

How it works? Why it has got such difference in memory after two years and between compilers? Changing virtual machine get this strange result?

I spent 3 hours on it.But I find it is expected to use "short" at last!!!

How to solve this problem using c++ ? My pick is  #MLE 14. I use (10^5 + 1000)*4 + 10^5 * 2
 = 589,84375 kilobytes of memory. I have no idea how to optimize it even more(

Edited by author 20.08.2020 02:34

Edited by author 20.08.2020 02:34

just a joke

Edited by author 18.09.2019 20:08

I tried so many time until I change `#include<bits/stdc++.h>` to `#include<stdio.h>`.

And then I did a small experience: for the same code,
Visual C++ 2017 -- 612 KB
Visual C 2017 -- 620 KB
GCC 7.1 / Clang++ 4.0.1 -- 652 KB
G++ 7.1 -- 700 KB

Hope it helps~

Yeah! I did it! I spent about 4 hours to solve this problem =)

C++ costs 200 kb (Visual C++ and 400 kb other compilers).

#include<bits/stdc++.h>
using namespace std;
int main(){
    long N,i,stack_id,num;
    string code;
    const string push="PUSH";
    vector< stack<int> > stacks;


    cin>>N;

    for(i=0;i<N;i++){
        cin>>code;

        if(code==push){
            cin>>stack_id>>num;

            if(stack_id>stacks.size()){
                stacks.push_back( stack<int>() );
            }
            stacks[stack_id-1].push(num);

        }
        else{
            cin>>stack_id;

            cout<<stacks[stack_id-1].top()<<"\n";
            stacks[stack_id-1].pop();
        }
    }

    return 0;
}



I get correct output on the sample code though.

no bitwise shit needed, no storing 17 bits for indexes and no such stuff! just use unsigned stack* [1000] for the stacks (store elements in a dynamic array, reallocating memory for each push), and unsigned  top[1000] for the index of the top element. with this i got AC with 663 KB! good luck!

#include <iostream>
using namespace std;
struct duy{
    long long x; int y;
};
int n,x,last[1001];
long long  y;
duy m[100001];
char s[5];
int main()
{
    cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>s>>x;
        if(s[1]=='U'){
            cin>>y;
            m[i].x=y; m[i].y=last[x]; last[x]=i;
        }
        else{
            cout<<m[last[x]].x;
            last[x]=m[last[x]].y;
        }
    }
}

I hope somebody will explain me what's wrong with my program, cause I really dont understand why i get out of memory (900KB) when my program should use only about 700KB (no more than 750KB definetly!).
So pls help me smb. Now i try to explain my problem.
The only memory i use, i define out of main scope and i dont use any dynamic allocations. So, the definition looks like:

unsigned int length[MAXIMUMSTACKS];
unsigned int maxlength[MAXIMUMSTACKS];
unsigned int base[MAXIMUMSTACKS];
unsigned int stackPtr[MAXIMUMSTACKS];
unsigned char opbuf[OPSIZE * MAXOP];
unsigned int stack[MAXOP / 2];

where MAXIMUMSTACKS = 1000, OPSIZE = 5, MAXOP = 100000.

So, let's count all memory we may use: 4*1000 + 4*1000 + 4*1000 + 4*1000 + 500000 + 4*50000 = 16*1000 + 500000 + 200000 = 716000 bytes! I is about 700KB to be honest.
So, i dont inderstand, why my program get Memory Limit Error and use (as Timus says) 900KB(!). Pls, help me to fix it. Tell me what i dont understand. I give you the code of programm below.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MASK(k) ((1 << k) - 1)
#define OPSIZE 5
#define POPCODE 1000000001
#define MAXIMUMSTACKS 1000
#define MAXOP 100000

unsigned int N;
unsigned int length[MAXIMUMSTACKS];
unsigned int maxlength[MAXIMUMSTACKS];
unsigned int base[MAXIMUMSTACKS];
unsigned int stackPtr[MAXIMUMSTACKS];
unsigned char opbuf[OPSIZE * MAXOP];
unsigned int stack[MAXOP / 2];
char op[5];

unsigned short stnum;
unsigned int value;
unsigned int indx;


int main(int argc, char *argv[]) {

//    freopen("input.txt", "r", stdin);

    // init
    scanf("%u", &N);
    memset(opbuf, 0, N * OPSIZE);
    memset(length, 0, MAXIMUMSTACKS * sizeof(unsigned short));
    memset(maxlength, 0, MAXIMUMSTACKS * sizeof(unsigned short));

    // fill opbuf
    for (unsigned int i = 0; i < N; ++i) {

        scanf("%s%hu", op, &stnum);
        --stnum;

        indx = OPSIZE * i;

        opbuf[indx] = *((unsigned char*)&stnum);
        opbuf[indx + 1] = *((unsigned char*)&stnum + 1) & MASK(2);

        if (op[1] == 'U') {
            scanf("%u", &value);

            value = (value << 2);
            for (unsigned int j = 0; j < 4; ++j)
                opbuf[indx + 1 + j] += *((unsigned char*)&value + j);

            ++length[stnum];
            if (length[stnum] > maxlength[stnum]) {
                maxlength[stnum] = length[stnum];

                if (maxlength[stnum] > MAXOP / 2)
                    maxlength[stnum] = MAXOP / 2;
            }

        } else {
            value = (POPCODE << 2);
            for (unsigned int j = 0; j < 4; ++j)
                opbuf[indx + 1 + j] += *((unsigned char*)&value + j);

            --length[stnum];
        }
    }

    // create big memory block for stacks
    unsigned int prevLength = 0;
    unsigned int prevBase = 0;
    for (unsigned int i = 0; i < MAXIMUMSTACKS; ++i) {
        if (maxlength[i] == 0)
            continue;

        base[i] = prevBase + prevLength;
        stackPtr[i] = base[i];
        prevBase = base[i];
        prevLength = maxlength[i];
    }

    // process through opbuf
    for (unsigned int i = 0; i < N; ++i) {
        stnum = 0;
        value = 0;
        indx = OPSIZE * i;

        stnum += opbuf[indx];
        stnum += ((opbuf[indx + 1] & MASK(2)) << 8);

        for (unsigned int j = 0; j < 4; ++j)
            *((unsigned char*)&value + j) = opbuf[indx + 1 + j];

        value = ((value >> 2) & 0x3fffffff);

        if (value == POPCODE) {

            if (stackPtr[stnum] == base[stnum]) {
                stackPtr[stnum] = base[stnum] + maxlength[stnum] - 1;
            } else {
                stackPtr[stnum]--;
            }

            printf("%u\n", stack[stackPtr[stnum]]);
        } else {
            stack[stackPtr[stnum]] = value;

            if (stackPtr[stnum] == base[stnum] + maxlength[stnum] - 1)
                stackPtr[stnum] = base[stnum];
            else
                stackPtr[stnum]++;
        }
    }

    return 0;
}

Edited by author 20.08.2015 16:44

Didn't notice that problem is not for Java, so I solved it. Maybe someone will need the solution. Solution without checking of stacks for emptiness.


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class HelloWorld {

    public static void main (String[] args)     {
        HashMap<Integer,  ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        reader.nextLine();
        for (int i = 0; i < n; i++) {
            String command = reader.nextLine();
            StringTokenizer tokenizer = new StringTokenizer(command);
            command = tokenizer.nextToken();
            if ("PUSH".equals(command)) {
                int key = Integer.parseInt(tokenizer.nextToken());
                int value = Integer.parseInt(tokenizer.nextToken());
                if (map.containsKey(key)) {
                    map.get(key).add(0, value);
                }
                else {
                    map.put(key, new ArrayList<Integer>());
                    map.get(key).add(0, value);
                }
            }
            else if ("POP".equals(command)) {
                int key = Integer.parseInt(tokenizer.nextToken());
                if (map.containsKey(key)) {
                    System.out.println(map.get(key).get(0));
                    map.get(key).remove(0);
                }
            }

        }
    }
}

Edited by author 31.10.2016 23:24

Edited by author 31.10.2016 23:26

Look at this, and remember magic number.

#include<stdio.h>

using namespace std;

const int max_stacks = 1000;
const int max_blocks = 6000; // magic number
const int block_size = 25;

int block[max_blocks][block_size];
int current_top[max_blocks];
int next_block[max_blocks];
int prev_block[max_blocks];

int free_blocks[max_blocks];
int fb_top=-1;

int head[max_stacks];
int tail[max_stacks];
int full_size[max_stacks];

int mem_sz = max_stacks*3 + max_blocks*4 + max_blocks*block_size;

int stn;
int i;
int n;
int value;

void init()
{
 for (i=0;i<max_stacks;i++)
 {
  head[i] = -1;
  tail[i] = -1;
  full_size[i] = 0;
 }
 for (i=0;i<max_blocks;i++)
 {
  current_top[i] = -1;
  next_block[i] = -1;
  prev_block[i] = -1;
 }
 for (i=0;i<max_blocks;i++)
 {
  free_blocks[i] = i;
 }
 fb_top = max_blocks-1;
}

void raise()
{
    int x = 42;
    int y = (x-x)/(x-x);
    int z = x/y;
    fb_top = z;
}

int get_free_block()
{
    if (fb_top==-1)
        raise();
    return free_blocks[fb_top--];
}

void clear_tail ()
{
    if (tail[stn]==-1) raise();
    int b = tail[stn];
    tail[stn] = next_block[b];
    prev_block[tail[stn]] = -1;
    full_size[stn]-=block_size;
    if (full_size<0) raise();

    free_blocks[++fb_top] = b;
    current_top[b] = -1;

    next_block[b] = -1;
    prev_block[b] = -1;
}

void push()
{
    if (head[stn]==-1)
    {
        int free = get_free_block();
        head[stn] = free;
        tail[stn] = free;

        current_top[free] = 0;
        block[free][0] = value;
        next_block[free] = -1;
        prev_block[free] = -1;
    }
    else if (current_top[head[stn]]==block_size-1)
    {
        if (full_size[stn]>n-i+2*block_size)
        {
            clear_tail();
        }
        int free = get_free_block();
        current_top[free] = 0;
        block[free][0] = value;

        next_block[head[stn]] = free;
        prev_block[free] = head[stn];
        head[stn] = free;
    }
    else
    {
        block[head[stn]][++current_top[head[stn]]] = value;
    }
    full_size[stn]++;
}

int pop()
{
    if (current_top[head[stn]]==-1) raise;
    int ans = block[head[stn]][current_top[head[stn]]--];
    if (current_top[head[stn]]==-1)
    {
        int cur = head[stn];
        head[stn] = prev_block[head[stn]];
        next_block[head[stn]]=-1;
        next_block[cur] = -1;
        prev_block[cur] = -1;
        free_blocks[++fb_top] = cur;
    }
    full_size[stn]--;
    return ans;
}


ok, if magic number == 6000, it got WA 15
magic number == 6004, WA 15
magic number == 6005, AC
magic number == 6006, AC
magic number == 6500, WA 15

How it can be?

Если вы поменяли компиляторы, то нужно сделать реджардж по задаче т.к. мои старые решения уже не проходят (да и вообще, если пересдавать старые АС, то память в них увеличилась, а вот время как-то непонятно ведет, где-то упало до 0.001, а там где было 0.5 сейчас стало 1.5)

Remember to remove any possible padding of the struct: for example, in MSVC do

#pragma pack(push, 1)

before the struct definition.

#include<vector>
#include<stack>
#include<iostream>
int main()
{
    int noOfInstructions = 0;
    std::cin>> noOfInstructions;

    std::vector< std::stack< int > > myVectorOfStacks;
    myVectorOfStacks.reserve( 1001 );
    for( int inx = 0; inx < 1001; ++inx )
    {
         myVectorOfStacks.push_back( std::stack<int>() );
    }

    char instruction[3];
    int stackNumber = 0;
    int stackValue = 0;

    for( int inx = 0; inx < noOfInstructions; ++inx )
    {
        std::cin>> instruction;

        std::cin>> stackNumber;
        std::stack< int > & tempStack = myVectorOfStacks.at( stackNumber );

        if( instruction[1] == 'U' )
        {
            std::cin>> stackValue;
            tempStack.push( stackValue );
        }
        else
        {
             std::cout<< tempStack.top()<< "\n";
             tempStack.pop();
        }
    }

    return 0;
}

#include<vector>
#include<stack>
#include<iostream>
int main()
{
    int noOfInstructions = 0;
    std::cin>> noOfInstructions;

    std::vector< std::stack< int > > myVectorOfStacks;
    myVectorOfStacks.reserve( 1001 );
    for( int inx = 0; inx < 1001; ++inx )
    {
         myVectorOfStacks.push_back( std::stack<int>() );
    }

    char instruction[3];
    int stackNumber = 0;
    int stackValue = 0;

    for( int inx = 0; inx < noOfInstructions; ++inx )
    {
        std::cin>> instruction;

        std::cin>> stackNumber;
        std::stack< int > & tempStack = myVectorOfStacks.at( stackNumber );

        if( instruction[1] == 'U' )
        {
            std::cin>> stackValue;
            tempStack.push( stackValue );
        }
        else
        {
             std::cout<< tempStack.top()<< "\n";
             tempStack.pop();
        }
    }

    return 0;
}

i got 0.531 sec for this code
#include <stdio.h>
#include <stdlib.h>

typedef unsigned int type;

struct stack{
    type* value;
    int cnt;
    int size;
};

#define delta 4

#define getnum(num) do {\
    (num) = 0; \
    char c; \
    while(1) { \
        c = fgetc(stdin); \
        if((c<'0')||(c>'9')) break; \
        (num)*=10; \
        (num)+=c-'0'; \
    }\
}while(0)

#define putnum(num) do { \
    char str[16]; \
    char *it = &str[15];*it = 0; \
    if((num)==0) { fputc('0', stdout); } \
    else { \
        while(num) { \
            --it; \
            *it = (char)((num)%10)+'0'; \
            (num)/=10; \
        } \
        while(*it) { \
            fputc(*it, stdout); \
            ++it; \
        } \
    }\
    fputc('\n', stdout); \
} while(0);

struct stack st[1000] = {0};
int main() {
    int cnt;
    getnum(cnt);
    while(cnt--){
        int id;
        char c,i;
        i=0;
        while((c = getchar())!=' ')
            ++i;
        getnum(id);
        --id;
        if(i>3) {
            st[id].cnt++;
            if(st[id].cnt > st[id].size) {
                st[id].size+=delta;
                st[id].value = (type*)realloc(st[id].value,
                                st[id].size*sizeof(type));
            }
            getnum(st[id].value[st[id].cnt-1]);
        }
        else {
            st[id].cnt--;
            putnum(st[id].value[st[id].cnt]);
            if(st[id].cnt+delta<st[id].size) {
                st[id].size-=delta;
                st[id].value = (type*)realloc(st[id].value,
                            st[id].size*sizeof(type));
            }
        }
    }
    return 0;
}

if set delta to 6, then i got MLE on test #12 =/
i broke my brain.
Sorry for my English