Submission #75537933

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
/*
！！！！！x, y 逆転注意！！！！！
*/
int H, W, N;
int h[212345], w[212345];
int cmp_h(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (h[a] > h[b]) - (h[a] < h[b]);
}
int cmp_w(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (w[a] > w[b]) - (w[a] < w[b]);
}
int hidx[212345], widx[212345];
int ans_y[212345], ans_x[212345];
void skip_h(int* left_h) {
  while (*left_h > 0 && ans_y[hidx[*left_h - 1]] > 0) (*left_h)--;
}
void skip_w(int* left_w) {
  while (*left_w > 0 && ans_y[widx[*left_w - 1]] > 0) (*left_w)--;
}
void solve(int height, int width, int offset_y, int offset_x, int left_h, int left_w) {
  if (skip_h(&left_h), left_h > 0 && h[hidx[left_h - 1]] == height) {
    int idx = hidx[--left_h];
    ans_y[idx] = offset_y;
    ans_x[idx] = offset_x;
    solve(height, width - w[idx], offset_y, offset_x + w[idx], left_h, left_w);
  } else if (skip_w(&left_w), left_w > 0 && w[widx[left_w - 1]] == width) {
    int idx = widx[--left_w];
    ans_y[idx] = offset_y;
    ans_x[idx] = offset_x;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

/*
！！！！！x, y 逆転注意！！！！！
*/

int H, W, N;
int h[212345], w[212345];

int cmp_h(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (h[a] > h[b]) - (h[a] < h[b]);
}

int cmp_w(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (w[a] > w[b]) - (w[a] < w[b]);
}

int hidx[212345], widx[212345];
int ans_y[212345], ans_x[212345];

void skip_h(int* left_h) {
	while (*left_h > 0 && ans_y[hidx[*left_h - 1]] > 0) (*left_h)--;
}

void skip_w(int* left_w) {
	while (*left_w > 0 && ans_y[widx[*left_w - 1]] > 0) (*left_w)--;
}

void solve(int height, int width, int offset_y, int offset_x, int left_h, int left_w) {
	if (skip_h(&left_h), left_h > 0 && h[hidx[left_h - 1]] == height) {
		int idx = hidx[--left_h];
		ans_y[idx] = offset_y;
		ans_x[idx] = offset_x;
		solve(height, width - w[idx], offset_y, offset_x + w[idx], left_h, left_w);
	} else if (skip_w(&left_w), left_w > 0 && w[widx[left_w - 1]] == width) {
		int idx = widx[--left_w];
		ans_y[idx] = offset_y;
		ans_x[idx] = offset_x;
		solve(height - h[idx], width, offset_y + h[idx], offset_x, left_h, left_w);
	}
}

int main(void) {
	int i;
	if (scanf("%d%d%d", &H, &W, &N) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &h[i], &w[i]) != 2) return 1;
	}
	for (i = 0; i < N; i++) {
		hidx[i] = i;
		widx[i] = i;
	}
	qsort(hidx, N, sizeof(*hidx), cmp_h);
	qsort(widx, N, sizeof(*widx), cmp_w);
	solve(H, W, 1, 1, N, N);
	for (i = 0; i < N; i++) {
		printf("%d %d\n", ans_y[i], ans_x[i]);
	}
	return 0;
}

/*

必ず「縦幅が全体の縦幅と同じブロック」または「横幅が全体の横幅と同じブロック」があるはず
前者があったら、それを左から配置していき、残りの部分で再帰
後者でも上から配置して同様

このとき、ここで扱った幅はここで全部消費するので、残った部分に配置するのはそれ未満のみのはず

*/

Submission Info

Judge Result