QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196255#6961. XOR Subsequenceyiyiyi#AC ✓784ms33564kbC++141.6kb2023-10-01 14:50:432023-10-01 14:50:44

Judging History

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

  • [2023-10-01 14:50:44]
  • 评测
  • 测评结果:AC
  • 用时:784ms
  • 内存:33564kb
  • [2023-10-01 14:50:43]
  • 提交

answer

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#include<set>
#define int long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define forE(i,x) for(int i=head[x];i;i=nxt[i])
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e6+5;
const int maxm=2e6+5;
const int mod=998244353;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*f;
}

int a[maxn],p[maxn];
int b[maxn];
bool flag=1;
int ans[maxn],cnt;
map<int,int> vis;
inline void solve(int l,int r)
{
	ans[++cnt]=a[l];
	if(l==r) return;
	rep(i,l+1,r) vis[a[i]]++;
	int tail=l;
	rep(i,l+1,r) 
	{
		if(vis[a[i]]&&(!vis[a[i]^a[l]])) {flag=0;break;}
		if(!vis[a[i]]) continue;
		if(vis[a[i]^a[l]]) vis[a[i]^a[l]]--,vis[a[i]]--,b[++tail]=a[i];
	}
	rep(i,l+1,r) vis[a[i]]=0;
	if(flag==0) return;
	sort(b+l+1,b+tail+1);
	rep(i,l+1,tail) a[i]=b[i];
	solve(l+1,tail);
	if(flag==0) return;
}
signed main()
{
	int T=read();
	p[0]=1;rep(i,1,21) p[i]=p[i-1]*2; 
	while(T--)
	{
		int n=read();flag=1;cnt=0;
		int tot=p[n]-1;
		rep(i,1,p[n]-1) a[i]=read();
		sort(a+1,a+tot+1);
		solve(1,tot);
		if(!flag) {puts("-1");continue;}
		rep(i,1,cnt) printf("%lld ",ans[i]);
		puts("");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 784ms
memory: 33564kb

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