Andrew Stankevich’s Contest #9解题报告 » ZOJ2700

ZOJ2700
ZOJ2700.cpp


#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 150;	// !!128!!WA!!

struct BPolynomial : vector<bool> {
	bool read(FILE* fp = stdin) {
		int n;
		if (fscanf(fp, "%d", &n) == EOF) {
			return false;
		}
		resize(n + 1);
		for (BPolynomial::reverse_iterator i = rbegin(); i != rend(); ++i) {
			fscanf(fp, "%d", &n);
			*i = (n != 0);
		}
		return true;
	}

	void write(FILE* fp = stdout) const {
		if (empty()) {
			fputs("-1", fp);
		} else {
			fprintf(fp, "%d ", (int)size() - 1);
			for (BPolynomial::const_reverse_iterator i = rbegin(); i != rend(); ++i) {
				fputs(*i ? " 1" : " 0", fp);
			}
			fputc('\n', fp);
		}
	}

	bool operator[](int i) const {
		return 0 <= i && i < (int)size() ? vector<bool>::operator[](i) : false;
	}

	void trim() {
		while (!(empty() || back())) {
			pop_back();
		}
	}
};

bool solve(int m, int n, bool a[MAXN * 3][MAXN], bool b[MAXN * 3], bool y[MAXN]) {
	static int p[MAXN * 3];
	int r = 0, c = 0;
	/*
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			putchar('0' + a[i][j]);
		}
		putchar('=');
		putchar('0' + b[i]);
		puts("");
	}
	puts("=");
	*/
	while (r < m && c < n) {
		int rr = -1;
		for (int i = r; i < m; ++i) {
			if (a[i]1) {
				rr = i;
				break;
			}
		}
		if (rr != -1) {
			for (int j = c; j < n; ++j) {
				swap(a[r][j], a[rr][j]);
			}
			swap(b[r], b[rr]);
			for (int i = r + 1; i < m; ++i) {
				if (a[i]1) {
					a[i]1 = false;
					for (int j = c + 1; j < n; ++j) {
						if (a[r][j]) {
							a[i][j] = !a[i][j];
						}
					}
					if (b[r]) {
						b[i] = !b[i];
					}
				}
			}
			p[r] = c;
			++r;
		}
		++c;
	}

	/*
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			putchar('0' + a[i][j]);
		}
		putchar('=');
		putchar('0' + b[i]);
		puts("");
	}
	puts("=");
	*/
	for (int i = r; i < m; ++i) {
		if (b[i]) {
			return false;
		}
	}

	c = n - 1;
	for (int i = r - 1; i >= 0; --i) {
		while (c > p[i]) {
			y1 = false;
		}
		y1 = b[i];
		for (int j = n - 1; j > c; --j) {
			y1 ^= a[i][j] && y[j];
		}
		--c;
	}
	while (c >= 0) {
		y1 = false;
	}
	return true;
}

int main() {
	BPolynomial a, b, c;
	bool x[MAXN * 3][MAXN], y[MAXN * 3], z[MAXN];
	int m, n;

	while (a.read() && b.read() && c.read()) {
		n = max(a.size(), max(b.size(), c.size()));
		m = 3 * n;
		for (int i = 0; i <= m; ++i) {
			for (int j = 0; j <= n; ++j) {
				x[i][j] = a[i - 2 * j] ^ b[i - j];
			}
			y[i] = c[i];
		}

		if (solve(m + 1, n + 1, x, y, z)) {
			BPolynomial ans;
			ans.insert(ans.end(), z, z + n + 1);
			ans.trim();
			ans.write();
		} else {
			puts("no solution");
		}
		puts("");
	}
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//2176431 	2010-04-25 14:56:48 	Accepted 	2700 	C++ 	40 	180 	watashi@Zodiac
Leave a Reply