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

i rewrote it without using strings and "namespace std" but MLE10   again( may be it is unreal problem? i think it can't be solved without array for 10^5 elements.... wrong cheker?

I keep two big arrays:
dword a[100000]
word nx[100000]
int f[1000]

bits 0..30 of 'a' - value
bits 0..15 of 'nx' together with 31th bit of 'a' - index of next item in the same stack
'f' - index of the top for corresponding stack

>together with 31th bit of 'a'

how can i write it?
i have ML((

#include <iostream.h>

struct aaa
{
 unsigned a :30;
 unsigned n :14;
}data[100001];

struct bbb
{
 unsigned a :14;
}pop[1001];

int main()
{
int n;
cin >> n;
char c;
unsigned int a,b,ss=0;
for(int i=0; i<n; i++)
{
cin >> c;
cin >> c;

if(c=='U')
{
cin >> c;
cin >> c;
cin >> a >> b;
data[ss].a=b;
data[ss].n=pop[a].a;
pop[a].a=ss;
ss++;
}else
{
cin >> c;
cin >> a;
cout << data[pop[a].a].a << endl;
data[pop[a].a].a=0;
pop[a].a=data[pop[a].a].n;
}
}
return 0;
}

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

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;
}

When you push item 'v' to stack 'i', you perform:

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

when you pop item from stasck 'i', you perform:

cout << get_value(f[i]);
f[i] = get_next(f[i]);

Another approach does not use bit manipulationson, but relies on fact that every output value requires two commands in the input (push and pop).

i just use dynamic arrays and nothing more :)
int* a[1001];
int len[1001];

void add(int ind,int data)
{
    len[ind]++;
    a[ind]=(int*)realloc(a[ind],len[ind]*4);
    a[ind][len[ind]-1]=data;
}

int del(int ind)
{
    --len[ind];
    int res=a[ind][len[ind]];
    a[ind]=(int*)realloc(a[ind],len[ind]*4);
    return res;
}
it accepts with large time but with extra small memory

Strange, Oracle, that shouldn't work on hard test cases.
Not only because of time, but because of memory too.

I've used
short s[100000],
long  a[100000],
long  top[1000].

Time - 0.234
Memory - 721 KB

Edited by author 25.01.2009 03:19

Edited by author 25.01.2009 03:19

ID 2260315 Oracle[Lviv NU] 1220 C++ Accepted 0.765 529 KB

I read input several times and get AC in C++.

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

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;
}


Edited by author 14.09.2009 18:47