In the first stage of most solutions, they are using $$$n$$$ splitting the minerals into $$$2$$$ piles, such that each pair of minerals have $$$1$$$ mineral in each pile.

However, they do not obtain any additional information from this stage. Let's fix that!

This is my first optimization. Let us randomly shuffle the minerals. Consider the minerals only in $$$[1,n]$$$, we will split them into $$$2$$$ piles $$$A$$$,$$$B$$$ and $$$C$$$ such that for minerals who has $$$2$$$ occurances in $$$[1,n]$$$, one of them in pile $$$A$$$ and $$$B$$$. While for minerals who has only $$$1$$$ occurance in $$$[1,n]$$$, they are in pile $$$C$$$. We can find these piles in $$$2n-|A|$$$ queries. However, we only need to do our "matching" on piles $$$A$$$ and $$$B$$$ now. Then we match $$$C$$$ with the corresponding $$$C$$$ of $$$[n+1,2n]$$$. The expected size of $$$|C|$$$ is $$$\frac{1}{2} n$$$. So with an additional $$$\frac{3}{2} n$$$ queries, we split our matchings into sizes $$$\frac{1}{4}n$$$,$$$\frac{1}{4}n$$$,$$$\frac{1}{2}n$$$. This saves around $$$\frac{3}{4} n$$$ queries.

The second optimization is to realize that if we order $$$A$$$ and $$$B$$$ by their index, then we should expect that the first $$$\frac{1}{4}$$$ of $$$B$$$ should only correspond to the first $$$\frac{3}{4}$$$ of $$$A$$$. So this gives us an optimization. Let us label the first and last $$$\frac{1}{4}$$$ $$$A$$$ with the same labels in our matching. For example, with $$$n=8$$$, we label them $$$[1,2,3,4,5,6,1,2]$$$. If we are lucky, one of the label points to a mineral in the first $$$\frac{1}{4}$$$ of $$$B$$$ and we save $$$2$$$ queries whenever this happens. I estimate this happens $$$\frac{1}{12} n$$$ of the time, so we save about $$$\frac{1}{6} n$$$ queries from this optimization.

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n=50000;
int arr[100005];

signed main(){
	for (int x=0;x<2*n;x++) arr[x]=x+1;
	shuffle(arr,arr+2*n,rng);
	
	cout<<n<<endl;
	for (int x=0;x<n;x++) cout<<arr[2*x]<<" "<<arr[2*x+1]<<endl;
}