QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197751 | #6961. XOR Subsequence | PPP# | AC ✓ | 225ms | 10348kb | C++17 | 1.5kb | 2023-10-02 19:27:38 | 2023-10-02 19:27:39 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
void solve()
{
ll n;
cin >> n;
ll n2 = (1LL<<n);
vector<ll> a(n2);
for (ll i=1;i<n2;i++) cin >> a[i];
sort(a.begin(),a.end());
vector<ll> A;
for (ll p=0;p<n;p++)
{
ll x = a[1];
A.push_back(x);
vector<ll> b;
for (ll i=0;i<(1<<(n-p));i++)
{
if (x==0 and i%2!=0) continue;
if (x!=0 and (x^a[i])<a[i]) continue;
b.push_back(a[i]);
//b.push_back(a[i]^x);
}
if (b.size()!=(1<<(n-p-1)))
{
cout << -1 << "\n";
return;
}
vector<ll> c = b;
sort(a.begin(),a.end());
for (ll i=0;i<(1<<(n-p-1));i++)
{
b.push_back(b[i]^x);
}
sort(b.begin(),b.end());
for (ll i=0;i<(1<<(n-p));i++)
{
if (a[i]!=b[i])
{
cout << -1 << "\n";
return;
}
}
a = c;
}
for (ll x: A) cout << x << " ";
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//#ifdef DEBUG
// freopen("input.txt", "r", stdin);
//#endif
ll T = 1;
cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 225ms
memory: 10348kb
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