Codeforces: Squares and not squares

Problem Link: Squares and not squares

Editorial: At first we can pre compute square numbers from 0 to 31623, as 31623*31623 = 1000014129, which is greater than 10⁹.

Then we will take two seperate vectors, one for storing square numbers and other for non square numbers. We can store them at the time of taking input. Simply binary searching in the pre computed square numbers vector would be greate.
Now, we will count how many square numbers are there in the square vector. Say it is count1. And number of non squared number would be count2 = n - count1. Now-->

1. If count1 == n/2, then the answer is zero.
2. If count1 > n/2, then we need to make some of our squared numbers into non squared number.
3. If count1 < n/2, then we need to make some of the non squared number to squared number.

count1 > n/2:
We need to check what is the maximum number of the squared numbers. If max_value is <=0, then for each squared number to make a non squared number we need to add +2 if the number is zero (0) else +1.
For 0, we should add +2 to make it 2, as 2 is not a squared number, but 1 is a square number. And we need to make (  count1- n/2 ) non_squared numbers.

count1 < n/2:

Now we need to find the closest squared number for each element of our non squared vector. Simply iterate through all the values from non squared vector and we will find upper_bound of each element in our pre computed square vector. We will take another vector to store the minimum value we got from each element via upper_bound. Finally we will sort the vector, and print the sum of the first (  n/2 - count1 ) elements from that vector.
Here is the solution of mine : solution