USACO Party Lamps

Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
ID: wcr19961
PROG: lamps
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn = 110;
int sta[maxn];
string ans[20];
int main() {
freopen("lamps.in", "r", stdin);
freopen("lamps.out", "w", stdout);
int n, c;
scanf("%d%d", &n, &c);
int x;
while (~scanf("%d", &x) && ~x) {
sta[x - 1] = 1;
}
while (~scanf("%d", &x) && ~x) {
if (sta[x - 1] == 1) {
puts("IMPOSSIBLE");
return 0;
}
sta[x - 1] = -1;
}
int S = 1 << 4, cnt = 0;
for (int i = 0; i < S; ++i) {
int k = __builtin_popcount(i);
if (k == 4 && (c < 4 || c & 1)) {
continue;
}
if (k == 3 && (c < 3 || (c & 1) == 0)) {
continue;
}
if (k == 2 && (c < 2 || (c & 1))) {
continue;
}
if (k == 1 && (c & 1) == 0) {
continue;
}
bool ok = true;
for (int j = 0; j < n; ++j) {
x = 1;
if (i & 1) {
x ^= 1;
}
if ((i & 2) && (j & 1)) {
x ^= 1;
}
if ((i & 4) && (j & 1) == 0) {
x ^= 1;
}
if ((i & 8) && j % 3 == 0) {
x ^= 1;
}
if ((sta[j] == -1 && x == 1) || (sta[j] == 1 && x == 0)) {
ok = false;
}
ans[cnt] += char('0' + x);
}
if (ok) {
++cnt;
} else {
ans[cnt] = "";
}
}
if (!cnt) {
puts("IMPOSSIBLE");
}
sort(ans, ans + cnt);
for (int i = 0; i < cnt; ++i) {
puts(ans[i].c_str());
}
return 0;
}

支付宝扫码领红包