The problem statement site e-olymp.com

Elevator

In the center of the city of New-Donetsk, a skyscraper was built with a huge number of floors. It also has an underground part, the number of floors of which is also incredibly large. A person who enters this skyscraper from the street gets to the floor with the number 0. The floors above him have positive numbers, and the negative numbers below. There is an elevator in the skyscraper. However, for certain reasons, it cannot stop on some floors. The elevator has two buttons - "up" and "down." When you press the "up" button, the elevator rises to the nearest floor where it can stop. When you press the "down" - goes down to the nearest such floor. Repeatedly pressing the button causes the elevator to perform the required action the appropriate number of times, without stopping at intermediate floors. The boy Vasya decided to ride this elevator. He entered the elevator on the ground floor and began to press the buttons.

Write a program to find the path that Vasya does.

Input data

The first line contains two integers K and N (0 ≤ K, N ≤ 10 ^ 5) - the number of floors on which the elevator does not stop, and the number of movements of the elevator, respectively. The second line contains K integers l1, l2, ..., lK (-10 ^ 9 ≤ l1 <... <lK ≤ 10 ^ 9) defining the numbers of these floors. It is guaranteed that all these numbers are different from 0. The third line contains N integers that define the commands that Vasya gave when he was in the elevator. The sign of the number identifies the button (the positive button corresponds to the "up" button, the negative - "down"), and its absolute value - the number of clicks. All numbers do not exceed 10 ^ 6 in absolute value.

Output

Output N numbers - the numbers of the floors on which the elevator stopped after each of Vasya's teams.

The code passes 82% due to exceeding the time limit

#include <stdio.h> #include <cmath> #include<set> using namespace std; int main() { set<long long> noset; long long k , n , curr = 0 , current = 0 , count = 0 , cur ,ioo; scanf("%lld %lld" , &k , &n); for(long long i = 0;i < k;i++) { scanf("%lld" , &ioo); noset.insert(ioo); } //quickSort(0 , k-1 , no); for(long long i = 0;i < n;i++) { scanf("%lld" , &curr); if(curr == 1) { do { current++; }while(noset.count(current)); printf("%lld" , current); } else if(curr == -1) { do { current--; }while(noset.count(current)); printf("%lld" , current); } else if(curr > 0) { count = 0; cur = current; while(count < abs(curr)) { do { current++; }while(noset.count(current)); count++; } printf("%lld" , current); } else if(curr < 0) { count = 0; cur = current; while(count < abs(curr)) { do { current--; }while(noset.count(current)); count++; } printf("%lld" , current); } printf(" "); } }
  • PS If you can not decide, then you should not put a minus to it, but simply ask a clarifying question - Denis Timchuk
  • Thank you, but somehow we ourselves will figure out what to do. - user227465
  • I just don’t understand why to do it, if I just asked for help and that's it - Denis Timchuk
  • I zaminusoval because I do not consider the Olympiad questions suitable for SO. Please do not confuse with the review of the code or specific questions on the class of tasks or algorithms. In addition - a minus is a reason to figure out what is wrong with the question, and not to leave a comment describing the negative and also with recommendations on who and how to do. - user227465
  • one
    I mean that in the current formulation of the question I see only a desire to take some kind of olympiad test there. There is no benefit from such a question for you or for the community. Although it can be altered in the question of what I listed in the previous comment. - user227465

1 answer 1

1) And who can give a reference to the task on the e-Olymp? The search for this “New Donetsk” is not there, and it looks like an element of the special Olympiad. That's what the cons come.

2) Of course, the solution is terribly inefficient in time. If one team takes up to 10 ^ 6 iterations over a set of 10 ^ 5 numbers, then we will spend up to 16 million elementary actions on one team. And a very non-cash friend.

What should be done. 1. Discard set in favor of the sorted vector. This will immediately increase the cache friendliness. 2. Search is not carried out across the entire width of the set, and starting from the current position. 3. Making the increment is not single, but immediately for the whole team.

The scheme is as follows. Let current be the current coordinate. Let pos be the current position (iterator) in a vector such that the invariant is executed

 lower_bound(begin(noset), end(noset), current) == pos

i.e,

 *(pos-1) < current <= *pos

(of course, with an eye on the edges of the vector)

If we want to increment the + command up, then

  • First, take, and jump without thinking about the non-stop floors:

     current1 = current + command; pos1 = lower_bound(pos, end(noset), current1); // инвариант, однако!

  • calculate how many floors we whistled:

     command1 = distance(pos, pos1); // или pos1 - pos.

  • on these floors we should not have pressed the button once more, but we pressed; let's compensate (that's why I called this number command1):

     current2 = curren1 + command1; pos2 = lower_bound(pos1, end(noset), current2); command2 = pos2 - pos1;

  • and so on, until the commandT becomes 0.

That is, modeling one command looks like this

 while (command > 0) { current += command; new_pos = lower_bound(pos, end(noset), current); command = new_pos - pos; // положительное или 0 pos = new_pos; } while (command < 0) { current += command; new_pos = lower_bound(begin(noset), pos, current); command = new_pos - pos; // отрицательное или 0 pos = new_pos; }

Is there an underwater rake here? Yes, of course, there is. If we have many, many floors in a row non-stop, and we jumped to the very beginning of this series, then new_pos will become equal to 1. We increment the command by one, jump to the second floor of the series, increment by one, jump to the third ... And so we will be individually go until we leave. And the next command, say, "-1". And we will get to the very end of the series, and we will start to descend individually ...

What can we do in this case: let's get two more vectors that answer the question: where is the beginning and where is the end of the series. Then the command up will be worked out like this:

 current += command; new_pos = lower_bound(pos, end(noset), current); command = new_pos - pos; pos = new_pos; if (pos != end(noset) && current == *pos) current = lasts[pos-begin(noset)];

And the team down - respectively,

 if (pos != end(noset) && current == *pos) current = firsts[pos-begin(noset)];

It is clear why in both cases we check for end (noset)? Because pos is obviously in the interval begin (noset) .. end (noset), where end is the iterator of the end, after the last element. In principle, we cannot jump over the front edge, this is how lower_bound works.

Well, we will need preprocessing — fill the firsts and lasts vectors so that for the first and last non-stop floors in the firsts and lasts series are equal to the value of this floor, and for the middle floors - see the neighbors before and after.

Filling in these arrays is easy and simple. We go up - we stretch the knowledge about the beginning of the series. We go down - we stretch the knowledge about the end of the series.

 for (i=0; i<K; ++i) firsts[i] = (i>0 && noset[i-1]+1 == noset[i]) ? firsts[i-1] : noset[i]; for (i==K-1; i>=0; --i) lasts[i] = (i<K-1 && noset[i]+1 == noset[i+1]) ? lasts[i+1] : noset[i];

Perhaps it can even be expressed by higher order functions from STL. But the cycle will come down.

  • e-olymp.com/ru/problems/3008 Thank you very much !! - Denis Timchuk
  • Just need to check for errors ± 1. I wrote a thought, not ready-made pieces of the solution. - Nickolay Merkin