On making an action, the cookie closest to Takahashi’s current coordinate \(X\) is always either “the largest coordinate less than \(X\)” or “the smallest coordinate greater than \(X\).” If these values can be retrieved fast enough, the problem can be solved.

Solution 1: ordered set

C++ has a data structure called “set,” which supports all of the following operations in \(O(\log N)\) time:

• Insert an element to the set.
• Remove an element from the set.
• Retrieve the largest value less than X in a set.
• Retrieve the smallest value greater than X in a set.

Therefore, the problem can be solved by managing the cookie coordinates in a set while simulating Takahashi’s actions, in a total of \(O(N\log N)\) time.

Writer’s solution (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	set<int>s;
	for(int i=0;i<n;i++){
		int ai;
		cin >> ai;
		s.insert(ai);
	}
	
	long long ans=0;
	int pos=0;
	for(int i=0;i<n;i++){
		auto it=s.lower_bound(pos);
		int nxt;
		if(it==s.begin()){
			nxt=*it;
		}else if(it==s.end()){
			nxt=*--it;
		}else{
			int cand1=*it;
			int cand2=*--it;
			if(abs(cand1-pos)<abs(cand2-pos)){
				nxt=cand1;
			}else{
				nxt=cand2;
			}
		}
		ans+=abs(nxt-pos);
		s.erase(nxt);
		pos=nxt;
	}
	cout << ans << endl;
}

Solution 2: two pointers

Sort the coordinates of the cookies, and prepare two queues: one stores negative coordinates and pops out the elements closer to the origin first; the other stores positive coordinates and pops out the elements closer to the origin first.

At any moment, the next cookie that Takahashi picks out is the front element of either queue. Therefore, by managing the cookie coordinates in two queues while simulating Takahashi’s actions, the problem can be solved in \(O(N)\) time after sorting.

In the sample code below, queues are not explicitly used, but the same mechanism is achieved by a list and variables containing the indices taken out next.

Writer’s solution (Python)

N=int(input())
A=list(map(int,input().split()))

N+=1
A.append(0)
A.sort()
P=A.index(0)
L=P-1
R=P+1
ans=0

pos=0
for _ in range(N-1):
  if L==-1:
    ans+=A[R]-pos
    pos=A[R]
    R+=1
  elif R==N:
    ans+=pos-A[L]
    pos=A[L]
    L-=1
  else:
    if pos-A[L]<=A[R]-pos:
      ans+=pos-A[L]
      pos=A[L]
      L-=1
    else:
      ans+=A[R]-pos
      pos=A[R]
      R+=1

print(ans)