Grakn Forces 2020 : F. Two Different

なんか変な問題。
https://codeforces.com/contest/1408/problem/F

問題

整数Nが与えられる。
N要素の整数列Aを考える。初期値ではA[i]=iである。
1～Nの間の2値を取り、1～Nを返す関数f(x,y)を考える。
f(x,y)がどんな関数であっても、以下を満たすQ組の整数対(X[i],Y[i])の並びの1例を示せ。

• 以下をi=1～Qまで繰り返す。
  • A[X[i]]とA[Y[i]]を、f(X[i],Y[i])で同時に上書きする。

最終的にAには2通り以下の値しか登場しない。

解法

Nが2の倍数でない場合、N以下の最大の2の累乗を2^Mとする。
同じ値を持つ長さ(2^k)の配列が2つある場合、それらを合わせることで同じ長さを持つ2^(k+1)の配列を作ることができる。
これらを用いて、Prefix (2^M)要素の値をそろえたのち、Suffix (2^M)要素の値をそろえればよい。

int N,M;
vector<pair<int,int>> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	M=1;
	while(M*2<=N) M*=2;
	FOR(i,16) {
		FOR(j,M) if((j&(1<<i))==0 && (j|(1<<i))<M) V.push_back({j+1,(j|(1<<i))+1});
	}
	if(M<N) {
		FOR(i,16) {
			FOR(j,M) if((j&(1<<i))==0 && (j|(1<<i))<M) V.push_back({N-(j|(1<<i)),N-j});
		}
	}
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
}

まとめ

Div混合とはいえこれでF問題か…。