又一场四题手速场，很自闭，莫名其妙的WA了好几发，QAAAAQ

---

A. Ehab Fails to Be Thanos

time limit per test1 second memory limit per test256 megabytes

You're given an array aa of length 2n2n. Is it possible to reorder it in such way so that the sum of the first nn elements isn't equal to the sum of the last nn elements?Input

The first line contains an integer nn (1≤n≤10001≤n≤1000), where 2n2n is the number of elements in the array aa.

The second line contains 2n2n space-separated integers a1a1, a2a2, ……, a2na2n (1≤ai≤1061≤ai≤106) — the elements of the array aa.Output

If there's no solution, print "-1" (without quotes). Otherwise, print a single line containing 2n2n space-separated integers. They must form a reordering of aa. You are allowed to not change the order.
Examplesinput

3
1 2 2 1 3 1

output

2 1 3 1 1 2

input

1
1 1

output

-1

Note

In the first example, the first nn elements have sum 2+1+3=62+1+3=6 while the last nn elements have sum 1+1+2=41+1+2=4. The sums aren't equal.

In the second example, there's no solution.

签个到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x7f7f7f7f;
int n,a[maxn];
int main(){
	cin>>n;
	rep(i,1,n*2) scanf("%d",&a[i]); sort(a+1,a+1+2*n);
	int sum1=0,sum2=0;
	rep(i,1,n) sum1+=a[i];
	rep(i,n+1,2*n) sum2+=a[i];
	if(sum1==sum2) puts("-1");
	else {
		rep(i,1,2*n) printf("%d ",a[i]);
	}
}

---

B. Ehab Is an Odd Person

time limit per test1 second memory limit per test256 megabytes

You're given an array aa of length nn. You can perform the following operation on it as many times as you want:

• Pick two integers ii and jj (1≤i,j≤n)(1≤i,j≤n) such that ai+ajai+aj is odd, then swap aiai and ajaj.

What is lexicographically the smallest array you can obtain?

An array xx is lexicographically smaller than an array yy if there exists an index ii such that xi<yixi<yi, and xj=yjxj=yj for all 1≤j<i1≤j<i. Less formally, at the first index ii in which they differ, xi<yixi<yiInput

The first line contains an integer nn (1≤n≤1051≤n≤105) — the number of elements in the array aa.

The second line contains nn space-separated integers a1a1, a2a2, ……, anan (1≤ai≤1091≤ai≤109) — the elements of the array aa.Output

The only line contains nn space-separated integers, the lexicographically smallest array you can obtain.
Examplesinput

3
4 1 7

output

1 4 7 

input

2
1 1

output

1 1 

Note

In the first example, we can swap 11 and 44 since 1+4=51+4=5, which is odd.

若原数列有奇有偶，则一定可以得到升序排列的数列（参考冒泡排序），如果只有奇数或者只有偶数，那么就不变。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int INF=0x7f7f7f7f;
int n,a[maxn];
int main(){
	cin>>n;
	int odd=0,even=0;
	rep(i,1,n){
		scanf("%d",&a[i]);
		if(a[i]%2) odd=1;
		else even=1;
	}
	if(odd&&even) sort(a+1,a+1+n);
	rep(i,1,n) printf("%d ",a[i]);	
}

---

C. Ehab and a Special Coloring Problem

time limit per test1 second memory limit per test256 megabytes

You're given an integer nn. For every integer ii from 22 to nn, assign a positive integer aiai such that the following conditions hold:

• For any pair of integers (i,j)(i,j), if ii and jj are coprime, ai≠ajai≠aj.
• The maximal value of all aiai should be minimized (that is, as small as possible).

A pair of integers is called coprime if their greatest common divisor is 11.Input

The only line contains the integer nn (2≤n≤1052≤n≤105).Output

Print n−1n−1 integers, a2a2, a3a3, ……, anan (1≤ai≤n1≤ai≤n).

If there are multiple solutions, print any of them.
Examplesinput

4

output

1 2 1 

input

3

output

2 1

Note

In the first example, notice that 33 and 44 are coprime, so a3≠a4a3≠a4. Also, notice that a=[1,2,3]a=[1,2,3] satisfies the first condition, but it's not a correct answer because its maximal value is 33.

借鉴素数筛法的思想构造数列

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int INF=0x7f7f7f7f;
int ans[maxn];
int main(){
	int n;cin>>n;
	int pos=0;
	rep(i,2,n){
		int flag=0;
		for(int j=i;j<=n;j+=i){
			if(!ans[j]){
				if(!flag) pos++,flag=1;
				ans[j]=pos;
			}
		}
	}
	rep(i,2,n) printf("%d ",ans[i]);
}

---

D. Ehab and the Expected XOR Problem

time limit per test1 second memory limit per test256 megabytes

Given two integers nn and xx, construct an array that satisfies the following conditions:

• for any element aiai in the array, 1≤ai<2n1≤ai<2n;
• there is no non-empty subsegment with bitwise XOR equal to 00 or xx,
• its length ll should be maximized.

A sequence bb is a subsegment of a sequence aa if bb can be obtained from aa by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.Input

The only line contains two integers nn and xx (1≤n≤181≤n≤18, 1≤x<2181≤x<218).Output

The first line should contain the length of the array ll.

If ll is positive, the second line should contain ll space-separated integers a1a1, a2a2, ……, alal (1≤ai<2n1≤ai<2n) — the elements of the array aa.

If there are multiple solutions, print any of them.
Examplesinput

3 5

output

3
6 1 3

input

2 4

output

3
1 3 1 

input

1 1

output

0

Note

In the first example, the bitwise XOR of the subsegments are {6,7,4,1,2,3}{6,7,4,1,2,3}.()

题目对子序列的异或值有要求，这是比较难维护的，应该想办法转化为单点的问题；
于是我们构造数组ans[i]表示前缀1~i的异或值，那么答案序列的b[i]显然就是ans[i]^ans[i-1];
由于任意一个子区间都可以用ans[i]^ans[j]表示，那么原题就转变为了任意ans[i]^ans[j]!=x，并且ans[i]!=ans[j]，考虑到范围只有1<<n，暴力扫一遍，如果已经有的数中没有能和当前枚举的数的异或为x的，那么就放入答案。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=0x7f7f7f7f;
int ans[maxn],pos;
set<int> s;
int main(){
	int n;ll x;cin>>n>>x;
	s.insert(0);
	rep(i,1,(1<<n)-1) if(s.find(x^i)==s.end()) s.insert(i),ans[++pos]=i;
	printf("%d\n",pos);
	rep(i,1,pos) printf("%d ",ans[i]^ans[i-1]);
	
}