//슬프다 엉엉.. O(1)으로 탐색할 방법을 너무 늦게 알았다..
//TLE 날 건 알고 있었는데 T.T
#include <stdio.h>
#include <map>
#include <vector>
#define ll long long
using namespace std;
struct block {
int idx;
ll h, w;
};
struct node {
ll x, y;
};
int main() {
int v[200010]={};
ll H, W, N;
ll posh=1, posw=1;
vector<block> choco;
node pos[200010];
map<ll, vector<ll>> Hmap, Wmap;
scanf("%lld %lld %lld", &H, &W, &N);
for(int i=0; i<N; i++) {
choco.push_back({0, 0, 0});
choco[i].idx=i+1;
scanf("%lld %lld", &choco[i].h, &choco[i].w);
Hmap[choco[i].h].push_back(i);
Wmap[choco[i].w].push_back(i);
}
ll nh=H, nw=W, cnt=N;
while(cnt) {
int i=-1; // h/w에서 탐색
while(!Hmap[nh].empty()) {
int ni=Hmap[nh].back();
Hmap[nh].pop_back();
if(!v[ni]) {
i=ni;
break;
}
}
if(i==-1) {
while(!Wmap[nw].empty()) {
int ni=Wmap[nw].back();
Wmap[nw].pop_back();
if(!v[ni]) {
i=ni;
break;
}
}
}
v[i]=1; //방문 O
int ridx=choco[i].idx; //진짜 인덱스
pos[ridx].x=posh, pos[ridx].y=posw;
posh+=choco[i].h;
if(posh>H) {
posh=H-nh+1;
posw+=choco[i].w;
}
if(nh!=choco[i].h) nh-=(choco[i].h%H);
if(nw!=choco[i].w) nw-=(choco[i].w%W);
cnt--;
}
for(int i=1; i<=N; i++) {
printf("%lld %lld\n", pos[i].x, pos[i].y);
}
}
To embed this project on your website, copy the following code and paste it into your website's HTML: