i've got a data:array[0..80000] of longint for save numbers and got AC! why there aren't tests like 100000 operators:
100000
PUSH 1 1
PUSH 1 2
...
PUSH 1 100000    ?

funny: data:array[0..100000] gives MLE 1
data:array[0..50000] gives WA 16
data:array[0..90000] gives WA 10
data:array[0..80000] gives AC...

First, very stupied method: used just 2 arrays for A and B values, 0.609s, 673KB.
Second, some hint: used multi-stack and for pointers at next element used unsigned short, 0.031s, 677KB.
Sorry, for bad english:-)

Edited by author 05.04.2010 05:23

Edited by author 05.04.2010 05:24

I tryed to minimize using of memory, but...


#include <cstdio>
#include <stack>
#include <map>

using namespace std;

map<unsigned int,stack<unsigned int> > m;

unsigned int n, i, b;
unsigned short a;
char c;


void main(void)
{
    scanf("%d",&n);

    for(i=0;i<n;i++){

        scanf("%s%s",c,c);

        if (c == 'U'){
            scanf("%d %d\n",&a,&b);
            m[a].push(b);
        }else{
            scanf("%d\n",&a);
            printf("%d\n",m[a].top());
            m[a].pop();
        }
    }
}

OK Denis Koshman, I did (thanks) but MLE test 10

why?

the program in all test use same memory and no use dinamic memory BUT MLE test 10

WHY?

is unbelive !!!

#include <iostream>
#include <string>
using namespace std;

unsigned int a[100000];
unsigned short b[100000];
int f[1000];

int nn=0;

inline int get_value(unsigned x)
{
return a[x] & 0x7FFFFFFF;
}

inline void set_value(unsigned x, unsigned v)
{
(a[x] &= 0x80000000) |= v;
}

inline int get_next(unsigned x)
{
return b[x] | ((a[x]>>31)<<16);
}

inline int set_next(unsigned x, unsigned v)
{
b[x] = v, (a[x] &= 0x7FFFFFFF) |= (v>>16)<<31;
}

void push (int pila, int v) {


int x = nn++; // 'nn' is global ever-growing variable
set_value(x, v);
set_next(x, f[pila]);
f[pila] = x;
}

void pop(int pila) {

cout << get_value(f[pila]) << endl;
f[pila] = get_next(f[pila]);

}


int main (void) {
int n;
int pila, v;

cin >> n;
string s;
unsigned int a,b,ss=0;

for(int i=0; i<n; i++)
{
cin >> s;
if(s=="PUSH")
{
cin >> pila;
cin >> v;

push(pila, v);
}

if(s=="POP")
{

cin >> pila;
pop (pila);

}
}
return 0;
}

What's so cool in this test? It pushes a lot into one stack or a lot into many stacks or what?
#include <iostream>
using namespace std;

struct elem
{
    unsigned int value;
    elem * next;
};
elem ** tree;
elem * push(elem * stack,unsigned int value)
{
    if(!stack)
    {
        stack = new elem;
        stack->value = value;
        stack->next = NULL;
        return stack;
    }
    else
    {
        elem * temp = new elem;
        temp->value = value;
        temp->next = stack;
        return temp;
    }
}
elem * pop(elem * stack,unsigned int & value)
{
    elem * temp = stack->next;
    value = stack->value;
    delete stack;
    return temp;
}
int main()
{
    tree = new elem* [1000];
    memset(tree,0,1000*4);
    int n;
    cin>>n;
    char str[5];
    int a;
    unsigned int b;
    for(int i = 0;i<n;++i)
    {
        cin>>str;
        if(str[1]=='U')
        {
            cin>>a;
            cin>>b;
            tree[a-1] = push(tree[a-1],b);

        }
        else
        {
            cin>>a;
            unsigned int value;
            tree[a-1] = pop(tree[a-1],value);
            cout<<value<<endl;

        }
    }

    return 0;
}

int main(int argc, char **argv){
    char s[6];
    int n,i,t;
    unsigned int a[100001];
    unsigned short b[100001];
    unsigned int f[1001];
    unsigned int d;
    scanf("%d",&n);
     for(i=0;i<n;i++){
        scanf("%s", s);
        if(s[1]=='U'){
            scanf("%d %u", &t, &d);
            a[i]=d<<1;
            b[i]=f[t]>>1;
            a[i]+=f[t]&1;
            f[t]=i;
        }else{
            scanf("%d",&t);
            printf("%u\n",a[f[t]]>>1);
            f[t] = (((int)b[f[t]])<<1)+(a[f[t]]&1);
      }
    }
    return 0;
}

I had MLE #1 with 2 arrays:
(C ++)
 int a[ 100000 ],
 short b[ 100000 ];
How to use 1 array instead of two???

I use :
int a[ 100000 ];
short num[ 100000 ];
And I have MLE #1!!!

My programm have MLE10, but when I add dispose after each POP operation it is AC. Why?
I think it don`t have to be like this in this problem.

I've solved this problem in Java!

http://acm.timus.ru/status.aspx?space=1&num=1220&author=23793

FAQ (http://acm.timus.ru/help.aspx?topic=java&locale=en) says "Here is the list of the problems which are not guaranteed to be solvable in Java: 1220, 1275, 1306."

Now 1220 may be removed from this list.

Russian version of the FAQ slightly more close to the truth. It says that problems except 1220, 1275 and 1306 may be solved in Java _without_significant_difficulties_. And this statement is true. 1220 _may_ be solved in Java, but with much more difficulty than in Pascal or C++.

why???
#include <iostream>
//#include <stdlib.h>
//#include <stdio.h>
#include <string.h>
using namespace std;
int i,o,tp,nm;
struct Tpart
{
    int val [24];
    int k;
    Tpart *lst;

};
char com[100];
Tpart stk[1024];
int Pop(Tpart *p)
{
    if(p->k>0) return p->val[--(p->k)];
    else
    {
        Tpart *e=p;
    p=p->lst;
    delete e;
    return p->val[--(p->k)];
    }};
void Push(Tpart *p, int val)
{
    if((p->k)<24) (p->val)[(p->k)++]=val;
        else
    {
        Tpart *uk= new Tpart;
        uk->lst=p;
        p=uk;
        p->k=0;
        (p->val)[(p->k)++]=val;
        }
    return;
}
int main() {

    int n; cin>>n;
    for(int j=0;j<n;j++)
    {
        cin>>com;
        if (strcmp(com,"PUSH")==0)
        {
            cin>>nm>>tp;
            Push(&stk[nm-1],tp);
            }
        if (strcmp(com,"POP")==0)
                {
                    cin>>nm;
                    cout<<Pop(&stk[nm-1])<<endl;}
        }
    return 0;
}

program t1220;
var i,k,m,n:longint;
    st:array[1..1000] of longint;
    a:array[0..100000] of longint;
    f:array[0..100000] of word;
    s:char;
begin
  readln(n);
  for i:=1 to n do
   begin
     read(s,s,s,s);
     if s='H' then
       begin
         readln(k,a[i]);
         f[i]:=st[k];
         st[k]:=i;
       end else
       begin
         readln(k);
         writeln(a[st[k]]);
         st[k]:=f[st[k]];
       end;
   end;
end.

I have got this in test 10 ,can anyone tell me ?
i only use an array 1..1000 of pointer ?
but my program :898 kb in test 10 ?
Const   Fi      ='';
        Go      ='';
        Limit   =1001;
Type    pt      =^pts;
                Pts=record
                        Data:Longint;
                        Link:Pt;
                end;
Var     f,g     :text;
        N       :Longint;
        St      :array[1..Limit] of pt;
Procedure OpenFile;
Begin
        Assign(f,fi); Reset(f);
        Assign(g,go); Rewrite(g);
End;

Procedure CloseFile;
begin
        Close(f); Close(g);
End;

Procedure Push(i,j:Longint);
var      p:pts;
Begin
        New(p); p^.data:=i;
        p^.link:=St[j]; ST[j]:=p;
End;

Function  Pop(j:Integer):Longint;
Var     p       :Pt;
Begin
        Pop := St[j]^.data;
        P := St[j]^.link;
        Dispose(St[j]);
        St[j] :=P;
End;

Procedure Solve;
Var     i,a,b:Longint;
        s:string;
        Ch:char;
Begin
        For i:=1 to 1000 do St[i]:=Nil;
        Readln(f,n);
        For i:=1 to n do
        BEgin
                S:='';
                While True do
                BEgin
                        Read(f,ch);
                        if ch=' ' then Break;
                        S:=S+ch;
                End;
                if S='PUSH' Then
                Begin
                        Readln(f,a,b);
                        Push(B,a);
                End
                Else
                Begin
                        Readln(f,a);
                        Writeln(g,Pop(a));
                End;
        End;
End;

Begin
        OpenFile;
        Solve;
        CloseFile;
End.

Edited by author 29.10.2008 09:53

MLE#10


#include <iostream>
#include <string>
using namespace std;
struct aaa
{
 unsigned int a :30;
}pop[1001],data[100001][2];
int main()
{
 int n;
 cin >> n;
 string s;
 unsigned int a,b,ss=0;
 for(int i=0; i<n; i++)
 {
  cin >> s;
  if(s=="PUSH")
  {
   cin >> a >> b;
   data[ss][0].a=b;
   data[ss][1].a=pop[a].a;
   pop[a].a=ss;
   ss++;
  }
  if(s=="POP")
  {
   cin >> a;
   cout << data[pop[a].a][0].a << endl;
   data[pop[a].a][0].a=0;
   pop[a].a=data[pop[a].a][1].a;
  }
 }
}

Edited by author 26.08.2008 15:33

Please someone give me hard test cases because my prog gets WA at 8 test. Dear authors, what is 8th test?

can somebody please suggest some test cases.

#include<iostream>
using namespace std;
#include<stack>
#include<vector>
int main()
{
    std::stack<int,std::vector<int> >val[1001];
    int k,i=0,n,m;
    cin>>k;
    char a[4];
    while(i<k)
    {
        cin>>a;
        if(a[1]=='U')
        {
            cin>>n>>m;
            val[n].push(m);
        }
else
            if(a[1]=='O')
            {
                cin>>n;
                cout<<val[n].top()<<endl;
                val[n].pop();
            }
            i++;
    }



            return 0;
}
Any idea how to optimize?Please help!
Thank!


Edited by author 10.11.2007 23:02