Posted on 2009-03-30 19:00
superman 閱讀(129)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 const int ON = 1, OFF = -1;
6
7 int n, c;
8 int FinalStatus[100];
9
10 string ans[16];
11 int ans_cnt;
12
13 bool x[100];
14
15 string x2string(bool x[], int n)
16 {
17 string ts;
18 for (int i = 0; i < n; i++)
19 ts += (x[i] + '0');
20 return ts;
21 }
22
23 void addAns()
24 {
25 string ts = x2string(x, n);
26
27 int i;
28 for (i = 0; i < ans_cnt; i++)
29 if (ans[i] == ts)
30 break;
31 if (i == ans_cnt)
32 ans[ans_cnt++] = ts;
33 }
34
35 bool check(int k)
36 {
37 if (k == 0)
38 {
39 if (c % 2 != 0)
40 return false;
41 }
42 else
43 if(c % k)
44 return false;
45 for (int i = 0; i < n; i++)
46 {
47 if (FinalStatus[i] == OFF && x[i] == true)
48 return false;
49 if (FinalStatus[i] == ON && x[i] == false)
50 return false;
51 }
52 return true;
53 }
54
55 void Button_4(int k)
56 {
57 if (check(k))
58 addAns();
59
60 for (int i = 0; i < n; i += 3) x[i] ^= 1;
61 if (check(k + 1))
62 addAns();
63 for (int i = 0; i < n; i += 3) x[i] ^= 1;
64 }
65
66 void Button_3(int k)
67 {
68 Button_4(k);
69
70 for (int i = 0; i < n; i += 2) x[i] ^= 1;
71 Button_4(k + 1);
72 for (int i = 0; i < n; i += 2) x[i] ^= 1;
73 }
74
75 void Button_2(int k)
76 {
77 Button_3(k);
78
79 for (int i = 1; i < n; i += 2) x[i] ^= 1;
80 Button_3(k + 1);
81 for (int i = 1; i < n; i += 2) x[i] ^= 1;
82 }
83
84 void Button_1(int k)
85 {
86 Button_2(k);
87
88 for (int i = 0; i < n; i++) x[i] ^= 1;
89 Button_2(k + 1);
90 for (int i = 0; i < n; i++) x[i] ^= 1;
91 }
92
93 int main()
94 {
95 freopen("lamps.in", "r", stdin);
96 freopen("lamps.out", "w", stdout);
97
98 cin >> n >> c;
99
100 int t;
101 while (true)
102 {
103 cin >> t;
104 if (t == -1) break;
105 FinalStatus[t - 1] = ON;
106 }
107 while (true)
108 {
109 cin >> t;
110 if (t == -1) break;
111 FinalStatus[t - 1] = OFF;
112 }
113
114 if (c == 0)
115 {
116 int i;
117 for (i = 0; i < n; i++)
118 if (FinalStatus[i])
119 break;
120 if (i == n)
121 {
122 for (int i = 0; i < n; i++)
123 cout << 1;
124 cout << endl;
125 }
126 else
127 cout << "IMPOSSIBLE" << endl;
128 exit(0);
129 }
130
131 //=========================
132 for (int i = 0; i < n; i++)
133 x[i] = true;
134
135 Button_1(0);
136
137 sort(ans, ans + ans_cnt);
138 for (int i = 0; i < ans_cnt; i++)
139 cout << ans[i] << endl;
140
141 if (ans_cnt == 0)
142 cout << "IMPOSSIBLE" << endl;
143
144 return 0;
145 }
146