You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道通信题。你提交的同一份程序会在每个测试点上从头启动两次，两次运行之间不保留内存中的状态。

第一次运行时，你会得到一个二进制串 $x$，需要输出一个长度不超过 $m$ 的二进制串 $y$。

两次运行之间，交互库会对 $y$ 至多修改一位：可能不修改，也可能将某个 0 改为 1 或将 1 改为 0，得到 $z$。

第二次运行时，你只会得到 $z$，需要准确恢复并输出原串 $x$。

输入与输出

第一次运行的输入为：

• 第一行为整数 1；
• 第二行为二进制串 $x$。

你应输出一行二进制串 $y$，其长度不超过 $m$。

第二次运行的输入为：

• 第一行为整数 2；
• 第二行为二进制串 $z$。

你应输出一行原二进制串 $x$。

样例测试中 $|x|=10,m=30$；其余测试中 $|x|=100000,m=100017$。两次运行的时间限制均为 $1$ 秒，内存限制均为 $512$ MB。你需要注意样例的前两个点是test，因此如果你直接假设长度为 100000 会发生段溢出。

样例

下面给出第一组合法的两次运行：

1
0000000000

000000000000000000000000000000

2
000000000000000000000000000000

0000000000

下面的第二次运行中，编码串有一位被修改：

2
000000000000100000000000000000

0000000000

样例只展示了某种正确编码。你输出的 $y$ 可以不同，只要满足长度限制并能在第二次运行中恢复 $x$。

参考实现

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define sc second
#define ll long long
using namespace std;
const int N = 1e5 + 30, M = (1 << 17) + 10; 
int opt, n, m; 
char s[N], t[N];
int a[M]; 
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	cin >> opt;
	int cnt = 0; 
	for (int i = 0; i < (1 << 17); i++)
	{
		if (__builtin_popcount(i) <= 1) continue;
		a[++cnt] = i;
	}
//	for (int i = 1; i <= n; i++)
//	int cur = 1; 
//	for (int i = 1; i <= cnt; i++)
//	{
//		cur = cur * 2 + 1;
//		while (cur >= (1 << 17)) cur -= (1 << 17);
//		swap(a[cur], a[i]);
//	} 
	swap(a[1], a[10]); 
	if (opt == 1)
	{
		scanf("%s", s + 1);
		n = strlen(s + 1);
		int x = 0;
		for (int i = 1; i <= n; i++) if (s[i] == '1') x ^= a[i];
		for (int i = 1; i <= n; i++) cout << s[i];
		for (int i = 0; i < 17; i++)
		{
			if ((x >> i) & 1) cout << 1;
			else cout << 0;
		}
	}
	else
	{
		scanf("%s", s + 1);
		m = strlen(s + 1);
		n = m - 17;
		int x = 0, u = 0; 
		for (int i = 1; i <= n; i++) if (s[i] == '1') x ^= a[i];
		for (int i = 0; i < 17; i++) if (s[i + n + 1] == '1') u += (1 << i);
		u ^= x;
		if (__builtin_popcount(u) <= 1) for (int i = 1; i <= n; i++) cout << s[i];
		else
		{
			for (int i = 1; i <= n; i++)
			{
				if (a[i] == u)
				{
					if (s[i] == '1') s[i] = '0';
					else s[i] = '1';
				}
			}
			for (int i = 1; i <= n; i++) cout << s[i];
		}
	}
	return 0;
}