Codeforces #647 Div1 C. Johnny and Megan's Necklace

これはライブラリがあると実装が軽め。
http://codeforces.com/contest/1361/problem/C

問題

N個の整数対がある。値は2^20未満の非負整数である。
これらを、(対の中の順番も含めて)任意に並べ替え、リング状に並べたとする。

異なる対の要素が隣接している箇所の美しさbは、両値u,vに対しu xor vを割り切る最大の2^bと定める(u xor v == 0 ならb=20とする)。
美しさの最小値が最大となるリングを構築せよ。

解法

美しさは高々20なので、美しさの大きい順に、その値を達成できるか試してみよう。
美しさbを達成できる場合、隣接する対の要素同士はmod 2^bを取った値が等しくなければならない。

そこで、無向グラフのオイラー閉路を考えよう。
(s,t)の対があったとき、(s mod 2^b)と(t mod 2^b)を辺でつなぐ。
このグラフにおいて、オイラー閉路が存在するなら、通った辺に沿って整数対を並べると解になる。

int N;
int A[1010101],B[1010101];
int X[1010101],Y[1010101];
int vis[1010101];

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	vector<int> E[MV];
	
	void dfs(int cur,int from=-1,int to=-1) {
		while(E[cur].size()) {
			int tar=E[cur].back();
			E[cur].pop_back();
			if(vis[tar/2]==0) {
				vis[tar/2]=1;
				if(tar%2) {
					dfs(X[tar/2],tar,tar^1);
				}
				else {
					dfs(Y[tar/2],tar,tar^1);
				}
			}
		}
		if(from>=0) {
			path.push_back(to);
			path.push_back(from);
		}
	}
	
	bool GetPath() { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0,c=-1;;
		FOR(i,MV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
			if(E[i].size()) c=i;
		}
		if(odd) return false;
		dfs(odd?fo:c);
		reverse(path.begin(),path.end());
		return path.size()==np;
	}
};

UndirectedEulerPath<1<<20> uep;

void solve() {
	int i,j,k,l,r,x,y; string s;

	scanf("%d",&N);
	FOR(i,N) scanf("%d%d",&A[i],&B[i]);
	
	for(i=19;i>=0;i--) {
		FOR(j,1<<20) uep.E[j].clear();
		ZERO(vis);
		uep.path.clear();
		FOR(j,N) {
			X[j]=A[j]&((1<<(i+1))-1);
			Y[j]=B[j]&((1<<(i+1))-1);
			uep.E[X[j]].push_back(2*j);
			uep.E[Y[j]].push_back(2*j+1);
			
		}
		if(uep.GetPath()) {
			auto p=uep.path;
			if(p.size()==2*N) {
				
				_P("%d\n",i+1);
				FORR(a,p) _P("%d ",a+1);
				_P("\n");
				return;
			}
		}
	}
	_P("0\n");
	FOR(i,2*N) _P("%d ",i+1);
	_P("\n");
	
}

まとめ

わかるとスッキリするタイプの問題。