택배 상하차

Simulation

평균 : 180'

---

sol : 165' 24''

• 수행 시간 : 149ms -> 10ms
• 메모리 : 0MB

Learnings

• 직사각형이어서 좌표를 전부 가지고 다닐 필요가 없었다.

After revise

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;

// 1-based
#define MAX_N 51
#define EMPTY 0
#define MAX_K 100

int n, m;
int grid[MAX_N][MAX_N];
int curTarget;

struct Post {
	int h;
	int w;
	int r;
	int c;
};

vector<Post> posts;

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

bool Fit(Post p) {
	for (int i = p.r; i < p.r + p.h; i++) {
		for (int j = p.c; j < p.c + p.w; j++) {
			if (!InGrid(i, j) || grid[i][j] != EMPTY) return false;
		}
	}
	return true;
}

void Drop() {
	posts.resize(MAX_K + 1);

	for (int p = 1; p <= m; p++) {
		int k, h, w, c;
		cin >> k >> h >> w >> c;

		Post cur = { h, w, 1, c };

		while (true) {
			cur.r++;
			if (!Fit(cur)) break;
		}
		cur.r--;

		posts[k] = cur;

		for (int i = cur.r; i < cur.r + cur.h; i++) {
			for (int j = cur.c; j < cur.c + cur.w; j++) {
				grid[i][j] = k;
			}
		}
	}
}

bool Remained() {
	for (int j = 1; j <= n; j++) {
		if (grid[n][j] != EMPTY) return true;
	}
	return false;
}

bool CanLeftPick(int id) {
	Post p = posts[id];

	int cur_c = p.c;

	while (cur_c > 1) {
		cur_c--;

		for (int i = p.r; i < p.r + p.h; i++) {
			if (grid[i][cur_c] != EMPTY) return false;
		}
	}

	return true;
}

bool CanRightPick(int id) {
	Post p = posts[id];

	int cur_c = p.c + p.w - 1;

	while (cur_c < n) {
		cur_c++;

		for (int i = p.r; i < p.r + p.h; i++) {
			if (grid[i][cur_c] != EMPTY) return false;
		}
	}

	return true;
}

void LeftPick() {
	int target = INT_MAX;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == EMPTY) continue;
			if (grid[i][j] == target) break;

			if (CanLeftPick(grid[i][j])) {
				if (grid[i][j] < target) target = grid[i][j];
			}
			break;
		}
	}

	curTarget = target;
}

void RightPick() {
	int target = INT_MAX;
	for (int i = 1; i <= n; i++) {
		for (int j = n; j >= 1; j--) {
			if (grid[i][j] == EMPTY) continue;
			if (grid[i][j] == target) break;

			if (CanRightPick(grid[i][j])) {
				if (grid[i][j] < target) target = grid[i][j];
			}
			break;
		}
	}

	curTarget = target;
}

void Remove() {
	Post p = posts[curTarget];

	for (int i = p.r; i < p.r + p.h; i++) {
		for (int j = p.c; j < p.c + p.w; j++) {
			grid[i][j] = EMPTY;
		}
	}
}

void Fall(int id) {
	Post p = posts[id];

	int cur_r = p.r;
	bool moved = false;

	while (true) {
		int next_r = cur_r + 1;

		if (next_r + p.h - 1 > n) break;

		bool can = true;
		for (int j = p.c; j < p.c + p.w; j++) {
			if (grid[next_r + p.h - 1][j] != EMPTY) {
				can = false;
				break;
			}
		}

		if (!can) break;

		cur_r++;
		moved = true;
	}

	if (!moved) return;

	// 기존 위치 제거
	for (int i = p.r; i < p.r + p.h; i++) {
		for (int j = p.c; j < p.c + p.w; j++) {
			grid[i][j] = EMPTY;
		}
	}

	// 위치 갱신
	posts[id].r = cur_r;

	// 다시 배치
	for (int i = cur_r; i < cur_r + p.h; i++) {
		for (int j = p.c; j < p.c + p.w; j++) {
			grid[i][j] = id;
		}
	}
}

void FallPhase() {
	for (int i = n - 1; i >= 1; i--) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == EMPTY) continue;
			Fall(grid[i][j]);
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;

	Drop();

	while (Remained()) {
		LeftPick();
		cout << curTarget << '\n';

		Remove();

		FallPhase();

		RightPick();
		cout << curTarget << '\n';

		Remove();

		FallPhase();
	}

	return 0;
}