[백준] 11670 초등 수학

문제

엘렌은 학생들에게 초등 수학을 가르치고 있고 곧 기말고사를 앞두고 있다. 기말고사는 n개의 질문들로 이루어져 있다.
각 질문마다 학생들은 한 쌍의 숫자들을 더하거나(+), 빼거나(-) 혹은 곱해야한다(*).

엘렌은 이미 n개의 숫자 쌍들을 골라놨다. 남은것은 이제 각 쌍의 숫자마다 어떠한 연산을 수행해야 할지 결정하는 것이었다.

학생들이 지루하지 않게 하기위해 엘렌은 n개의 연산결과들이 모두 다르게 하고 싶어했다.

엘렌이 시험을 잘 준비 할 수 있게 도와주자.

입력

첫째 줄에 순서쌍의 개수 n (1 ≤ n ≤ 2 500)이 입력된다.

다음 n개의 줄에 걸쳐서 순서쌍 a,b (−106 ≤ a, b ≤ 106)가 입력된다.

출력

입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다.
a와 3개의 연산자(+ 혹은 - 혹은  *)중 하나, b 그리고 = 와 연산결과이다. 모든 연산결과는 달라야한다.

만약 출력 할 수 있는 답이 여러개라면 아무거나 출력하고, 답이 없다면 “impossible” 을 출력한다.

 

이분 매칭 문제입니다.

이 문제에서 까다로웠던 점은 반대쪽 매칭 정점의 범위가 -10^6~10^6까지라는 점입니다.

따라서,,, 만들 수 있는 정점의 리스트를 작성하고 중복제거를 해준뒤에 인덱싱처리를 따로 해주어야합니다.

개수는 3*2500=7500이므로 가능합니다

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define mset(v) memset(v,0,sizeof(v))
#define IDX(v, x) lower_bound(v.begin(),v.end(), x) - v.begin()
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
ll N, a, b, cnt, v[8501], s[8501], d[8500];
vector<ll> nums;
pair<ll, ll> num[2526];
vector<ll> adj[2526];
bool dfs(int k) {
	if (v[k])return false;
	v[k] = 1;
	for (int r : adj[k]) {
		
		if (s[r] == -1 || dfs(s[r])) {
			s[r] = k;
			d[k] = r;
			return true;
		}
	}
	return false;
}
int main() {
	FAST;
	cin >> N;
	REP(i, N) {
		cin >> a >> b;
		num[i] = { a,b };
		nums.push_back(a + b);
		nums.push_back(a - b);
		nums.push_back(a * b);

	}
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	memset(s, -1, sizeof(s));
	REP(k, N) {
		auto [x, y] = num[k];
		adj[k].push_back(IDX(nums, x + y));
		adj[k].push_back(IDX(nums, x - y));
		adj[k].push_back(IDX(nums, x * y));

		mset(v);
		if (!dfs(k)) {
			cout << "impossible";
			return 0;
		}
	}
	REP(i, N) {
		auto [x, y] = num[i];
		ll target = nums[d[i]];

		if (x + y == target) {
			cout << x << " + " << y << " = " << target << "\n";
		}
		else if (x - y == target) {
			cout << x << " - " << y << " = " << target << "\n";
		}
		else if (x * y == target) {
			cout << x << " * " << y << " = " << target << "\n";
		}
	}

}