# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setters: Tejas Pandey,Utkarsh Gupta

Tester: Manan Grover, Abhinav Sharma

Editorialist: Devendra Singh

# DIFFICULTY:

2543

# PREREQUISITES:

# PROBLEM:

Chef has an array A of length N such that A_i = i.

In one operation, Chef can pick any two elements of the array, delete them from A, and append either their bitwise XOR or their bitwise OR to A.

Note that after each operation, the length of the array decreases by 1.

Let F be the final number obtained after N-1 operations are made. You are given an integer X, determine if you can get F=X via some sequence of operations.

In case it is possible to get F = X, print the operations too (see the section Output format for more details), otherwise print -1.

# EXPLANATION:

Let us handle the case when N=2 separately, when N is 2 only possible value of X is 3 as both `XOR`

and `OR`

of 1 and 2 result in 3. So if N is 2 and x!=3, answer is -1 otherwise both `XOR`

or `OR`

of 1 and 2 are acceptable answers.

If some bit in X is set to 1 which is not set to 1 in any number till N then there is no possible way to attain such X , Hence answer in this case is -1 too.

If N is a power of two then the most significant bit in N is set to 1 in only one number and is 0 in all other numbers less than N hence whether you take `XOR`

with this number or `OR`

with this number, this bit has to be set to 1 in X . If it is unset in X then the answer is -1

Otherwise it is always possible to construct the answer:

Consider the construction take `OR`

of all the elements in the array which are not a power of 2.

This way at least all the bits upto most significant bit of N( excluding it) will be set in the the number obtained.

## Proof

If N is a power of 2.Then since we take `OR`

with (2^{msb})-1. It sets all the bits upto msb of N in the number obtained.

Otherwise we take `OR`

of N with 2^{msb}-1 and this sets all the bits upto msb of N in the number obtained.

Now iterate on the bits from i=0 to the most significant bit of N. If it is set in X we take `OR`

with 2^i present in the array otherwise we take `XOR`

with 2^i present in the array.

(Since if N is a power of 2 then X will have most significant bit of N set, therefore we will take OR with N in the end.)

Thus we can get the final value same as X by this method.

# TIME COMPLEXITY:

O(N) or O(Nlog(N)) depending upon implementation for each test case.

# SOLUTION:

## Setter's solution

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, x;
cin >> n >> x;
int bk = 0;
for(int i = 20; i > 0; i--) {
if(n&(1LL<<i)) {
bk = (1LL<<(i + 1));
break;
}
}
if((n == 2 && x != 3) || ((n&(n - 1)) == 0 && (x&n) == 0) || x >= bk) {
cout << "-1\n";
continue;
}
if(n == 2) {
cout << "1 1 2\n";
continue;
}
set<int> s1, s2;
for(int i = 1; i <= n; i++) s1.insert(i);
for(int i = 0; i < 20; i++) {
if((1LL<<i) > n) break;
if((x&(1LL<<i)) == 0) {
s1.erase((1LL<<i));
s2.insert((1LL<<i));
}
}
int n1 = 0, n2 = 0;
if(s1.size()) {
n1 = (*(s1.begin()));
s1.erase(s1.begin());
while(s1.size()) {
int now = (*(s1.begin()));
cout << "1 " << n1 << " " << now << "\n";
n1 |= now;
s1.erase(s1.begin());
}
}
if(s2.size()) {
n2 = (*(s2.begin()));
s2.erase(s2.begin());
while(s2.size()) {
int now = (*(s2.begin()));
cout << "1 " << n2 << " " << now << "\n";
n2 |= now;
s2.erase(s2.begin());
}
}
if(n1 > 0 && n2 > 0) cout << "2 " << n1 << " " << n2 << "\n";
}
}
```

## Editorialist's Solution

```
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, x, msbx, msbn;
cin >> n >> x;
map<int, bool> ispow2;
if (n == 2 && x != 3)
{
cout << -1 << '\n';
return;
}
else if(n==2 && x==3)
{
cout<<1<<' '<<1<<' '<<2<<'\n';
return ;
}
for (int i = 0; i < 20; i++)
{
ispow2[1 << i] = true;
if ((1 << i) & n)
msbn = i;
if ((1 << i) & x)
msbx = i;
}
if (msbx > msbn)
{
cout << -1 << '\n';
return;
}
if (!ispow2[n] || (x & n))
{
int val = 0;
for (int i = 1; i <= n; i++)
{
if (!ispow2[i])
{
if (i > 3)
cout << 1 << ' ' << i << ' ' << val << '\n';
val |= i;
}
}
for (auto y : ispow2)
{
if (y.F > n || !y.S)
continue;
if (x & (y.F))
{
cout << 1 << ' ' << y.F << ' ' << val << '\n';
val |= y.F;
}
else
{
cout << 2 << ' ' << y.F << ' ' << val << '\n';
val ^= y.F;
}
}
}
else
{
cout << -1 << '\n';
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
```