「BZOJ1923」[SDOI2010]外星千足虫

Description

公元2089年6月4日,在经历了17年零3个月的漫长旅行后,“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局(NASA)研制发射,行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等23颗太阳系星球,并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下45.70米位置发现一批珍贵的活体生命样本,并将其带回检测。在带回的活体样本中,最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长,身体分为若干节。受到触碰时,会将身体卷曲成圆环形,间隔一段时间后才会复原活动。

有趣的还不止如此。研究人员发现,这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足,但足的总数一定是奇数条!虽然从外观难以区分二者,但通过统计足的数目,科学家们就能根据奇偶性判断出千足虫所属的星球。

作为J国派去NASA的秘密间谍,你希望参加这次研究活动以掌握进一步的情报,而NASA选拔的研究人员都是最优秀的科学家。于是NASA局长Charles Bolden出了一道难题来检测你的实力:

现在你面前摆有1…N编号的N只千足虫,你的任务是鉴定每只虫子所属的星球,但不允许亲自去数它们的足。Charles每次会在这N只千足虫中选定若干只放入“昆虫点足机”(the Insect Feet Counter, IFC)中,“点足机”会自动统计出其内所有昆虫足数之和。Charles会将这个和数mod 2的结果反馈给你,同时告诉你一开始放入机器中的是哪几只虫子。他的这种统计操作总共进行M次,而你应当尽早得出鉴定结果。

假如在第K次统计结束后,现有数据就足以确定每只虫子的身份,你就还应将这个K反馈给Charles,此时若K<M,则表明那后M-K次统计并非必须的。

如果根据所有M次统计数据还是无法确定每只虫子身份,你也要跟Charles讲明:就目前数据会存在多个解。

Input

第一行是两个正整数N, M。

接下来M行,按顺序给出Charles这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字,用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器:如果第i个字符是“0”则代表编号为i的虫子未被放入,“1”则代表已被放入。后面跟的数字是统计的昆虫足数mod 2的结果。

由于NASA的实验机器精确无误,保证前后数据不会自相矛盾。即给定数据一定有解。

Output

输出文件insect.out在给定数据存在唯一解时有N+1行,第一行输出一个不超过M的正整数K,表明在第K次统计结束后就可以确定唯一解;接下来N行依次回答每只千足虫的身份,若是奇数条足则输出“?y7M#”(火星文),偶数条足输出“Earth”。如果输入数据存在多解,输出“Cannot Determine”。

所有输出均不含引号,输出时请注意大小写。

Sample Input

1
2
3
4
5
6
3 5
011 1
110 1
101 0
111 1
010 1

Sample Output

1
2
3
4
4
Earth
?y7M#
Earth

HINT

对于20%20\%的数据,满足N=M20N=M\leq 20
对于40%40\%的数据,满足N=M500N=M\leq 500
对于70%70\%的数据,满足N500,M1,000N\leq 500,M\leq 1,000
对于100%100\%的数据,满足N1,000,M2,000N\leq 1,000,M\leq 2,000

Solution

异或方程组高斯消元板子题。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2100;
int n, m;

char s[N];
bitset<1100>sa[N];
bool sb[N];
bitset<1100>a[N];
bool b[N];
bool check(int x) {
for(int i = 1; i <= x; ++i) a[i] = sa[i], b[i] = sb[i];
for(int i = 1; i <= n; ++i) {
for(int j = i; j <= x; ++j) if(a[j][i - 1]) {
swap(a[i], a[j]);
swap(b[i], b[j]);
break;
}
if(!a[i][i - 1]) return 0;
for(int j = 1; j <= x; ++j) if(j != i && a[j][i - 1]){
a[j] ^= a[i];
b[j] ^= b[i];
}
}
return 1;
}


int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
scanf("%s", s);
for(int j = 0; j < n; ++j)
if(s[j] == '1') sa[i][j] = 1;
sb[i] = read();
}
int l = n - 1, r = m;

while(r - l > 1) {
int mid = (l + r) >> 1;
// printf("l=%d,r=%d,mid=%d,val=%d\n", l, r, mid, check(mid));
if(check(mid))
r = mid;
else l = mid;
}
if(!check(r)) {
puts("Cannot Determine");
} else {
writeln(r);
for(int i = 1; i <= n; ++i) puts(b[i] ? "?y7M#" : "Earth");
}
return 0;
}