Codeforces 277C (170C) Game

問題

nxmの方眼紙がある。
方眼紙には1x1刻みで縦線と横線が引かれている。
(ふちに線はひかれていないものとする)


この用紙を使って二人が次のようなゲームをする。

  • 二人が交互に手番をもつ。
  • 手番のプレイヤーは、格子点と格子点を結ぶ、水平または垂直な線分を引く。
  • 線分は、必ず長さ0以上のまだ線の引かれていない部分を含まなければならない。
  • 線分のひけなくなった人の負け。


最初からひかれている線分が与えられるとき、
(この線分は、重複があったりする)お互いが最善を尽くすとして、
どちらが勝つか出力せよ。

先手が勝つ場合は、先手の最初の手として適当なものをどれか一つ出力せよ。

制約条件

n, m≦10^9
k≦10^5

方針

縦の線、横の線がそれぞれ一つの山に対応するようなNimをやっていることに相当する。
山の石の数は、線のうち、消えていない部分の長さである。


なので、Nimの必勝法通り、各山のxorを取り、それが0なら後手勝ちで、そうでないなら先手勝ちである。
先手勝ちのとき、xorを0にするような手を打てばよい。


消えてない部分の長さは、累積和などを使って上手く求めてやる。

ソースコード

int w, h, k;
map<int, vector<pi> > tate, yoko;
map<int, int> tatelen, yokolen;

int calc(int &sz, int len, vector<pi> &v){
	sort(all(v));
	map<int, int> m;
	m[0] = m[len] = 0;
	
	rep(i, v.size()) m[v[i].first]++, m[v[i].second]--;
	int s = 0, p = 0;
	sz = 0;
	each(i, m){
		if(s == 0) sz += i->first - p;
		s += i->second;
		p = i->first;
	}
	return sz;
}
int calc2(int sz, int len, vector<pi> &v){
	map<int, int> m;
	m[0] = m[len] = 0;
	rep(i, v.size()) m[v[i].first]++, m[v[i].second]--;
	int s = 0, p = 0, sum = 0;
	each(i, m){
		if(s == 0){
			int t = i->first - p;
			if(sum <= sz && sz <= sum + t) return p + sz - sum;
			sum += t;
		}
		s += i->second;
		p = i->first;
	}
	assert(0);
}

int main(){
	cin >> w >> h >> k;
	rep(i, k){
		int x, y, X, Y;
		cin >> x >> y >> X >> Y;
		if(x > X) swap(x, X);
		if(y > Y) swap(y, Y);
		if(x == X) tate[x].pb(mp(y, Y));
		else yoko[y].pb(mp(x, X));
	}
	int sum = 0;
	each(i, tate) sum ^= calc(tatelen[i->first], h, i->second);
	each(i, yoko) sum ^= calc(yokolen[i->first], w, i->second);
	if((w - 1 - tate.size()) % 2) sum ^= h;
	if((h - 1 - yoko.size()) % 2) sum ^= w;
	
	if(sum == 0){
		cout << "SECOND" << endl;
		return 0;
	}
	cout << "FIRST" << endl;
	
	each(i, tatelen){
		int l = i->second;
		if((sum ^ l) <= l){
			int ans = calc2(tatelen[i->first] - (sum ^ l), h, tate[i->first]);
			cout << i->first << " " << 0 << " " << i->first << " " << ans << endl;
			return 0;
		}
	}
	each(i, yokolen){
		int l = i->second;
		if((sum ^ l) <= l){
			int ans = calc2(yokolen[i->first] - (sum ^ l), w, yoko[i->first]);
			cout << 0 << " " << i->first << " " << ans << " " << i->first << endl;
			return 0;
		}
	}
	if(tate.size() < w - 1 && (sum ^ h) <= h){
		for(int i = 1 ; i < w; i++) if(!tate.count(i)){
			cout << i << " " << 0 << " " << i << " " << h - (sum ^ h) << endl;
			return 0;
		}
	}
	for(int i = 1 ; i < h; i++) if(!yoko.count(i)){
		cout << 0 << " " << i << " " << w - (sum ^ w) << " " << i << endl;
		return 0;
	}
	
	return 0;
}