QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203724#6961. XOR SubsequenceMXYH875AC ✓173ms8704kbC++142.5kb2023-10-06 19:39:512023-10-06 19:39:52

Judging History

你现在查看的是最新测评结果

  • [2023-10-06 19:39:52]
  • 评测
  • 测评结果:AC
  • 用时:173ms
  • 内存:8704kb
  • [2023-10-06 19:39:51]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define x first
#define y second
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef unsigned long long ULL;
typedef pair<double,double> PDD;

const int N=1e6+10,mod=1e9+7,INF=0x3f3f3f3f;
int t;
int n;
int a[N];
int ans[33],num=0;
int s[N];
bool st[33];

int f(int u)
{
	int res=0;
	for(int i=0;i<n;i++)
	{
		if(u&(1<<i)) res^=ans[i];
	}
	return res;
}

bool check()
{
	
	int len=1;
	for(int i=1;i<(1<<n);i++)
	{
		s[len++]=f(i);
	}
//		printf("s= ");
//		for(int i=1;i<len;i++) printf("%d ",s[i]);
//		puts("");
//		printf("a= ");
//		for(int i=1;i<len;i++) printf("%d ",a[i]);
//		puts("");
	sort(s+1,s+len);
	for(int i=1;i<(1<<n);i++)
	{
		if(s[i]!=a[i]) return false;
	}
	return true;
}

int main()
{                                                                                                                          
	cin>>t;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<(1<<n);i++) scanf("%d",&a[i]);
		sort(a+1,a+(1<<n));
		num=0;
		for(int i=1;i<(1<<n);i*=2)
		{
			ans[num++]=a[i];
		}
		if(check())
		{
			for(int i=0;i<n;i++) printf("%d ",ans[i]);
			puts("");
		}
		else 
		{
			puts("-1");
		}
	}
	return 0;
}

/*
3
3
1 2 3 4 5 6 7
3
1 0 1 0 1 0 1
3
1 2 3 4 5 6 6
  
 */


/*
 *
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 173ms
memory: 8704kb

input:

4115
1
220426753
2
75752216 139004411 214624995
3
425320853 659634699 1040767902 61426054 620262285 1033998872 451979283
4
289669156 16842978 272957638 16779852 289737354 21236708 4456872 268501358 285213068 272894568 4524806 21299530 68270 285281058 268438464
5
288507119 704365180 764545802 9869220...

output:

220426753 
75752216 139004411 
61426054 425320853 620262285 
68270 4456872 16779852 268438464 
25699612 34220493 74041718 280650227 678684512 
-1
0 0 0 67108864 134217728 268435456 536870912 
136604 6052763 27897018 37591031 75573769 136661209 279830679 547648454 
2026397 2791316 8827893 17803262 38...

result:

ok 4115 lines