小Q与异或

NC219164. 小Q与异或

描述

小 Q 在思考一个奇怪的问题，这个问题是这样的：请给出一个长度为 ${n}$ 的序列 ${a}$ ，使其满足给出的 ${m}$ 个式子。

其中第 ${i}$ 个式子会给出两个参数 $p,x$ ，表示 ${\bigoplus_{i=1}^pa_i=x}$ 。

为了使题目变得更加简单，其中对于每一个 $i$ ， $a_i\in [1,2\times 10^{10}]$ 。

如果没有一个序列都满足给出的 $m$ 条柿子，请直接输出 $-1$ 。

输入描述

输入第一行有两个整数 ，表示序列的长度与式子的个数。

接下来  行，每行有两个整数，分别表示每个式子的参数 。

输出描述

本题将会使用 Special Judge。
只有一行包含  个整数，表示序列 。

示例1

输入:

5 2
1 2
3 4

输出:

2 2 4 1 1

说明:

示例2

输入:

6 1
2 4

输出:

6 2 4 3 1 4

示例3

输入:

2 2
1 2
2 2

输出:

-1

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 363ms, 内存消耗: 18424K, 提交时间: 2021-04-25 20:48:38

#include <bits/stdc++.h>
using namespace std;
int i,k,n,m,a[1000050],b[1000050],tmp,nmsl;
int main(){
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		a[i]=-1;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&k,&nmsl);
		if(a[k]!=-1&&a[k]!=nmsl){puts("-1");return 0;}
		a[k]=nmsl;
	}
	for(i=1;i<=n;i++){
		if(tmp==a[i]){puts("-1");return 0;}
		if(a[i]==-1){b[i]=rand();}
		else{b[i]=tmp^a[i];}tmp^=b[i];
	}
    printf("%d",b[1]);
	for(i=2;i<=n;i++){
		printf(" %d",b[i]);
	}
}

上一题

下一题

详情