1278.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1278 on 2005-11-12 at 15:11:14 */ 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAX = 128;

typedef pair<int, int> pii;

class Set {
public:
	int n;
	int contain[MAX];
	bool operator <(const Set& s) const {
		if(n < s.n) {
			return false;
		} else if(n > s.n) {
			return true;
		} else {
			int i;
			for(i = n-1; i >= 0; i--) {
				if(contain[i] < s.contain[i]) {
					return true;
				}
			}
			return false;
		}
	}
	void init();
	void insert(int);
	void print() const;
};
void Set::init() {
	n = 0;
}
void Set::insert(int a) {
	contain[n++] = a;
}
void Set::print() const {
	int i;
	for(i = n-1; i >= 0; i--) {
		if(i != n-1) {
			putchar(' ');
		}
		printf("%d", contain[i]);
	}
	putchar('\n');
}

class List {
private:
	int n[MAX];
	int top;
	int bottom;
public:
	void init(int);
	pii pop();
};
void List::init(int m) {
	int i;
	for(i = 0; i <= m; i++) {
		n[i] = i;
	}
	top = m;
	bottom = m-1;
}
pii List::pop() {
	pii k = pii(top, bottom);
	n[top]--;
	n[bottom]--;
	while(n[top] == 0) {
		top--;
		if(top == bottom) {
			bottom--;
		}
	}
	while(n[bottom] == 0) {
		bottom--;
	}
	return k;
}

int cmp(const void*, const void*);

int main()
{
	Set set[MAX];
	List list;
	pii k;
	int n, i, t = 0, m;
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			if(t != 0) {
				putchar('\n');
			}
			t++;
			m = n * (n + 1) / 2;
			if(m % 2 != 0) {
				printf("0\n");
			} else {
				m /= 2;
				list.init(n);
				for(i = 0; i < n; i++) {
					set[i].init();
				}
				for(i = 0; i < m; i++) {
					k = list.pop();
					set[i%n].insert(k.first);
					set[i%n].insert(k.second);
				}
				qsort(set, n, sizeof(Set), cmp);
				printf("%d\n", n);
				for(i = 0; i < n; i++) {
					set[i].print();
				}
			}
		}
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	if(*(Set*)a < *(Set*)b) {
		return -1;
	} else {
		return 1;
	}
}