Submission #70488654

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7;
int n;
pair<vi,vi> construct(int n) {
	vi ans1;
	vi ans2;
	//cout << n << endl;
	if(n == 1) {
		ans1.pb(0);
		ans2.pb(0);
		return make_pair(ans1, ans2);
	}
	if(n == 2) {
		ans1.pb(0);
		ans1.pb(1);
		ans2.pb(1);
		ans2.pb(0);
		return make_pair(ans1, ans2);
	}
	auto tmp = construct((n - 1) / 2);
	vi a = tmp.first;
	vi p = tmp.second;
	if(n % 2 == 1) {
		int mx = 0;
		for(auto&u : a)
			mx = max(mx, u);
		int h = 0;
		while((1 << h) <= mx) ++h;
		for(auto&u : a)
			ans1.pb(u);
		ans1.pb(a.back() + (1 << h));
		for(auto&u : a)
			ans1.pb(u + (3 << h));
		ans2.pb((1 << (h + 2)) - 1);
		L(i, 0, sz(p) - 1)
			ans2.pb(p[i] | (1 << h)), ans2.pb(p[i]);
		return make_pair(ans1, ans2);
	} else {
		int mx = 0;
		for(auto&u : a)
			mx = max(mx, u);
		int h = 0;
		while((1 << h) <= mx) ++h;
		for(auto&u : a)
			ans1.pb(u);
		ans1.pb(a.back() + (1 << h));
		ans1.pb(a.back() + (3 << h));
		for(auto&u : a)
			ans1.pb(u + (7 << h));
		ans2.pb((1 << (h + 3)) - 1);
		L(i, 0, sz(p) - 1)
			ans2.pb(p[i] | (3 << h)), ans2.pb(p[i] | (1 << h));
		ans2.pb(0);
		return make_pair(ans1, ans2);
	}
	return make_pair(ans1, ans2);
}
void Main(){
	
	cin >> n;
	auto u = construct(n);
	for(auto&x : u.first)
		cout << x << ' ';
	cout << '\n';
	for(auto&x : u.second)
		cout << x << ' ';
	cout << '\n';
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}

Submission Info

Judge Result