Codeforces #252 Div2 C. Valera and Tubes

CF252に参加。Div2回の割にDEが難しく、ABCをさっさと解くことしかできなかった。
Dは解いたもののWA。
http://codeforces.com/contest/441/problem/C

問題

NxMのグリッドの中にK個のチューブを配置したい。
各チューブは２マス以上の連結したマスで、隣接マスを一筆書きで書けるような形状を取る。

N,M,Kが与えられたとき、そのような配置を答えよ。

解法

以下のようにたどれば１個の長いチューブを配置できるので、後はK-1個分を２マスずつ取り、残りをK個目に割り当てればよい。

－－－－－┐
┌－－－－┘
└－－－－┐
┌－－－－┘
└－－－－－

int N,M,K;
vector<pair<int,int> > P;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(y,N) {
		FOR(x,M) {
			if(y%2==0) P.push_back(make_pair(y+1,x+1));
			else P.push_back(make_pair(y+1,M-x));
		}
	}
	FOR(i,K-1) {
		_P("%d %d %d %d %d\n",2,P[i*2].first,P[i*2].second,P[i*2+1].first,P[i*2+1].second);
	}
	x=(K-1)*2;
	_P("%d ",N*M-x);
	while(x<N*M) _P("%d %d ",P[x].first,P[x].second), x++;
	_P("\n");
}

まとめ

ここまではすんなり。