Softeer - 좌석관리

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=625 

Softeer

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <sstream>
#include <set>

using namespace std;

int N, M, Q;
map<int, pair<int, int>> employee;
set<int> complete;
vector<vector<int>> table;

int dist(pair<int, int> pos) {
	int d = 987654321;
	for (auto it = employee.begin(); it != employee.end(); ++it) {
		int x = pos.first - it->second.first;
		int y = pos.second - it->second.second;
		d = min(d, x * x + y * y);
		if (d < 2) return d;
	}
	return d;
}

pair<int, int> pos() {
	if (employee.empty()) return { 1, 1 };

	int d = 0;
	pair<int, int> pos = { 0, 0 };

	for (int i = 1; i < N; ++i) {
		for (int j = 1; j < M; ++j) {
			if (table[i][j] != 0)
				continue;

			int t = dist({ i, j });
			if (d < t && 2 <= t) {
				pos = { i, j };
				d = t;
			}
		}
	}
	return pos;
}

void f(string inout, int id) {
	auto pos_init = pair<int, int>{ 0,0 };

	if (inout == "In") {
		if (complete.count(id)) {
			printf("%d already ate lunch.\n", id);
			return;
		}

		if (employee.find(id) != employee.end()) {
			printf("%d already seated.\n", id);
			return;
		}

		auto cur = pos();
		if (cur == pos_init) {
			cout << "There are no more seats.\n";
			return;
		}

		table[cur.first][cur.second] = id;
		employee[id] = cur;
		printf("%d gets the seat (%d, %d).\n", id, cur.first, cur.second);
		return;
	}
	else {
		if (complete.count(id)) {
			printf("%d already left seat.\n", id);
			return;
		}

		if (employee.find(id) == employee.end()) {
			printf("%d didn't eat lunch.\n", id);
			return;
		}

		auto cur = employee[id];
		table[cur.first][cur.second] = 0;
		employee.erase(id);
		complete.insert(id);
		printf("%d leaves from the seat (%d, %d).\n", id, cur.first, cur.second);
	}
}

int main() {
	cin >> N >> M >> Q;
	++N, ++M;

	table.resize(N, vector<int>(M));
	

	for (int i = 0; i < Q; ++i) {
		string inout;
		int id;

		cin >> inout;
		cin >> id;

		f(inout, id);
	}

	return 0;
}