ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1220. Stacks

crazy problem, I'm out of ideas
Posted by dibrov.bor [Sumy State University] 16 Aug 2007 23:12
1 067 KB
used 30 bit structure with queue
struct cell {
   unsigned value : 30;
   cell (unsigned in) : value (in) {};
};
std::queue <cell> major;
ok, queue build with pointers, so lets soluted witout it

971 KB
used 30 bit structure with vector
std::vector <cell> major;
hm...
ok let's try other way


used indexing of values - there are 100'000 posible values, so let's indexing every value and storage indexes
std::map <int, int> i2v, v2i;
1 223 KB

bad way, well let's make crazy thing - build bit storage with next structure - for every value calculate number of max bit with help of next function
int length (unsigned in) {
   int result (0);
   while (in) {
      ++result;
      in >>= 1;
   };
   return result;
};
than push into storage last {length (value)} bits of value and than 5 bits, which content number of bits of this value (maximum value is 1'000'000 so maximum count of bits is 30, thats why counter of bits count must have 5 bits)
ok for example if PUSH value 5 [101]
length (5) return 3, we push into storage bits [101] and than five bits with length of value bits - 3 [00011]
std::list <unsigned char> major;
783 KB

...
yeah, last idea - use bit storage and indexing values
803 KB

guys, who solved this problem with C++ - you are genius, I am out of ideas, have smb other one ?
Re: crazy problem, I'm out of ideas
Posted by svr 17 Aug 2007 02:32
I solved it on 400KB but not very fast
I added data by 1000 size portions and was making
stable sort