Codeforces Round #126 (Div. 2) A : Cinema

問題概要

N*M(N,M<2000)の空きますがある。これからK(

解法

各(x, y)について、それより左側にある最小の空きマスと、それより右側にある最小の空きマスを計算しておく。各クエリに対しては、xについて全探索すれば計算量O(K*M)で目的地を見つけられる。また、データの更新は目的地のx座標を持つすべてのyに対して更新処理をすればやはりO(K*N)でできる。これで全体の計算量がO(K*(N+M))になるが、10^8とちょっと大きいので適当に枝刈りなどを加えるとACが得られる。

acceptされたコード

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 2000;
const int MAX_K = (int)(1e5);
const int INF = 1<<29;

int N, M, K;
bool filled[MAX_N][MAX_N];
int low[MAX_N][MAX_N], high[MAX_N][MAX_N];
int xs[MAX_K], ys[MAX_K];

void init() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d%d", xs+i, ys+i);
		--xs[i];
		--ys[i];
	}
}

void proc(int x, int y) {
	int mini = INF;
	for (int xx = max(0, x-10); xx < min(N, x+10); ++xx) {
		mini = min( mini, abs(xx - x) + abs(y - low[xx][y]) );
		mini = min( mini, abs(xx - x) + abs(y - high[xx][y]) );
	}
	++mini;
	int bx = -1, by = -1;
	for (int xx = max(0, x - mini); xx < N && x + mini >= xx; ++xx) {
		int d = abs(xx - x) + abs(y - low[xx][y]);
		if (d < mini) {
			mini = d;
			bx = xx;
			by = low[xx][y];
		}
		d = abs(xx - x) + abs(y - high[xx][y]);
		if (d < mini) {
			mini = d;
			bx = xx;
			by = high[xx][y];
		}
	}

	printf("%d %d\n", bx + 1, by + 1);
	filled[bx][by] = true;
	int l = (by == 0 ? -INF : low[bx][by-1]), h = (by == M - 1 ? +INF : high[bx][by+1]);
	for (int yy = by; yy < M && l < by; ++yy) {
		if (!filled[bx][yy]) {
			l = yy;
		}
		low[bx][yy] = l;
	}
	for (int yy = by ; yy >= 0 && h > by; --yy) {
		if (!filled[bx][yy]) {
			h = yy;
		}
		high[bx][yy] = h;
	}

}

void solve() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			low[i][j] = high[i][j] = j;
		}
	}
	for (int i = 0; i < K; ++i) {
		proc(xs[i], ys[i]);
	}
}

int main() {
	init();
	solve();

	return 0;
}