USACO 2.2.4 – Party Lamps

#include <cstdio>
#include <iostream>
#include <set>

using namespace std;

int main() {
	set<string> s;
	int lamps, N, C, ON, OFF, on = 0, off = 0;
	freopen("lamps.in", "r", stdin), freopen("lamps.out", "w", stdout);
	cin >> N >> C;
	C = (C % 2) ? (C > 3 ? 3 : C) : (C > 4 ? 4 : C);
	while (cin >> ON && ON != -1)   on  |= 1 << (5 - ((ON  - 1) % 6));
	while (cin >> OFF && OFF != -1) off |= 1 << (5 - ((OFF - 1) % 6));

	for (int  m = 0; m < 16; m++) {
		if (C < __builtin_popcount(m)) continue;
		lamps  = (m & 1 ? 0 : 63) ^ (m & 2 ? 21 : 0) ^ (m & 4 ? 42 : 0) ^ (m& 8 ? 36 : 0);
		if ((lamps & off) == 0 && (~lamps & on) == 0) {
			string b = "";
			for (int i = 0; i < N; i++)
				b += (((lamps >> (5 - (i % 6))) & 1) ? "1" : "0");
			s.insert(b);
		}
	}
	if (!s.size())
		puts("IMPOSSIBLE");
	else
		for (set<string>::iterator i = s.begin(); i != s.end(); i++)
			cout << *i << endl;
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: