how to solve this F!@#$%G problem?
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
Re: how to solve this F!@#$%G problem?
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?
Re: how to solve this F!@#$%G problem?
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
Re: how to solve this F!@#$%G problem?
>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;
}
Re: how to solve this F!@#$%G problem?
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;
}
Re: how to solve this F!@#$%G problem?
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]);
Re: how to solve this F!@#$%G problem?
Another approach does not use bit manipulationson, but relies on fact that every output value requires two commands in the input (push and pop).
Re: how to solve this F!@#$%G problem?
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
Re: how to solve this F!@#$%G problem?
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
Re: how to solve this F!@#$%G problem?
ID 2260315 Oracle[Lviv NU] 1220 C++ Accepted 0.765 529 KB
Re: how to solve this F!@#$%G problem?
I read input several times and get AC in C++.
Re: how to solve this F!@#$%G problem?
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