Submission #73314655

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int H,W,n,h[N],w[N];
unordered_map<int,int> cnt_h,cnt_w;
unordered_map<int,vector<int>> pos_h,pos_w;
pair<int,int> ans[N];

void dfs(int now_h,int now_w,int x = 1,int y = 1)
{
	if(cnt_h[now_h])
	{
		int pos = *(--pos_h[now_h].end());
		cnt_h[now_h]--;
		cnt_w[w[pos]]--;
		pos_h[now_h].pop_back();
		pos_w[w[pos]].erase(find(pos_w[w[pos]].begin(),pos_w[w[pos]].end(),pos));
		ans[pos] = {x,y};
		dfs(now_h,now_w - w[pos],x,y + w[pos]);
	}
	else if(cnt_w[now_w])
	{
		int pos = *(--pos_w[now_w].end());
		cnt_w[now_w]--;
		cnt_h[h[pos]]--;
		pos_w[now_w].pop_back();
		pos_h[h[pos]].erase(find(pos_h[h[pos]].begin(),pos_h[h[pos]].end(),pos));
		ans[pos] = {x,y};
		dfs(now_h - h[pos],now_w,x + h[pos],y);
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> H >> W >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> h[i] >> w[i];
		cnt_h[h[i]]++,cnt_w[w[i]]++;
		pos_h[h[i]].push_back(i);
		pos_w[w[i]].push_back(i);
	}
	dfs(H,W);
	for(int i = 1;i <= n;i++)
	{
		int x = ans[i].first,y = ans[i].second;
		cout << x << ' ' << y << "\n";
	}
	return 0;
}

Submission Info

Judge Result