Submission #1013545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013545		rainboy	Cutting a Rectangle (BOI24_rectangle)	C11	100 / 100	25 ms	3164 KiB

Main

#include <stdio.h>
#include <string.h>
 
#define N	100000
 
long long min(long long a, long long b) { return a < b ? a : b; }
 
unsigned int Z = 12345;
 
int rand_() {
	return (Z *= 3) >> 1;
}
 
int aa[N], bb[N], cc[N * 2], ii[N], hh[N * 2], n;
 
int *xx;
 
void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
 
		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}
 
int solve(long long a, long long b) {
	static char used[N];
	int i, iaa, iab, iba, ibb;
 
	memset(used, 0, n * sizeof *used);
	iaa = iab = iba = ibb = n - 1;
	while (a != 0 && b != 0) {
		while (iaa >= 0 && (used[iaa] || aa[iaa] > a))
			iaa--;
		while (iab >= 0 && (used[ii[iab]] || bb[ii[iab]] > a))
			iab--;
		while (iba >= 0 && (used[iba] || aa[iba] > b))
			iba--;
		while (ibb >= 0 && (used[ii[ibb]] || bb[ii[ibb]] > b))
			ibb--;
		if (a > b) {
			if (iaa >= 0 && aa[i = iaa] == a) {
				if (b < bb[i])
					return 0;
				used[i] = 1, b -= bb[i];
			} else if (ibb >= 0 && bb[i = ii[ibb]] == b) {
				if (a < aa[i])
					return 0;
				used[i] = 1, a -= aa[i];
			} else if (iba >= 0 && aa[i = iba] == b) {
				if (a < bb[i])
					return 0;
				used[i] = 1, a -= bb[i];
			} else
				return 0;
		} else {
			if (iba >= 0 && aa[i = iba] == b) {
				if (a < bb[i])
					return 0;
				used[i] = 1, a -= bb[i];
			} else if (iab >= 0 && bb[i = ii[iab]] == a) {
				if (b < aa[i])
					return 0;
				used[i] = 1, b -= aa[i];
			} else if (iaa >= 0 && aa[i = iaa] == a) {
				if (b < bb[i])
					return 0;
				used[i] = 1, b -= bb[i];
			} else
				return 0;
		}
	}
	return 1;
}
 
int main() {
	int m, m_, h, i;
	long long area;
 
	scanf("%d", &n);
	area = 0;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &aa[i], &bb[i]);
		area += (long long) aa[i] * bb[i];
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	xx = bb, sort(ii, 0, n);
	m = 0;
	for (i = 0; i < n; i++)
		if (area % aa[i] == 0 && solve(aa[i], area / aa[i]))
			cc[m++] = min(aa[i], area / aa[i]);
	for (h = 0; h < n; h++) {
		i = ii[h];
		if ((h == 0 || bb[i] != bb[ii[h - 1]]) && area % bb[i] == 0 && solve(bb[i], area / bb[i]))
			cc[m++] = min(bb[i], area / bb[i]);
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	xx = cc, sort(hh, 0, m);
	m_ = 0;
	for (h = 0; h < m; h++)
		if (m_ == 0 || cc[hh[m_ - 1]] != cc[hh[h]])
			hh[m_++] = hh[h];
	m = m_;
	printf("%d\n", m);
	for (h = 0; h < m; h++)
		printf("%d\n", cc[hh[h]]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:91:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d%d", &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 55 / 55