<PREV Problem:
Solved by 227 users: ...

Functions values caching

Time limit = 2 second(s)

Memory limit = 64 Mb

You're about to be kicked out of college. This is no surprise — you weren't attending your French classes and you didn't want to get a C for "Theory of Groups and Representations" (you asked for re-examination but didn't attend it going to the cinema with your girlfriend to watch "Enchanted" instead). There are also phys. culture, calculus, theor. mechanics... Eh!!!

Though, you may find an approach to your French prof. He runs a popular website dedicated to learning foreign languages. And this website works terribly slowly. Too many users are activly doing pair learning online.

The professor said he might help you if you "Speed up the site".

After brief looking througth database log yo found that database queries to the users table are way too often, and unresonable. The number of the site visitors is bounded at any moment and the profiles of currently surfing users may be stored in memory.

All you need is just to rewrite the function get_user(int user_id) so that it supports caching. The function returns user profiles stored in the database (we'll call user profiles just "users").

You made up the following caching algorithm. Let M be the cache size. A list of cached users must be stored. The list is constructed as follows. When the function is called with user_id as an argument you need to check whether the user with such id exists in the list and if it does, you must return the cached user, moving it to the beginning of the list. If it doesn't, you must call the database and place the user to the beginning of the list. If the list length is more than M (namely, M + 1), the last element must be deleted from it. This way the list always contains cached function values for the last M unique arguments.

You want to study the efficiency of caching depending on the value of M testing it on real data.

Input The size of cache M, 0 < M < 5000000, is written on the first line. A sequence of no more than 500000 integer numbers follows. Each number is in the range [0, 20000000].

Output For each number from the sequence output 0 if the cached value was used and 1 otherwise. Use space as a delimiter.

1 2 3 4 5
1 1 1 1 1
7 7 7 7 7
1 0 0 0 0
1 2 3 1 4 5 6 7 2 5 1 3 2
1 1 1 0 1 1 1 1 1 0 1 1 0

Artem Voroztsov, individual MIPT contest, 21 sep., 2008
20 sep. 2008

<PREV | Problem set | Search related messages | NEXT>

© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID =