Codechef June Cook-Off 2021 Solution | Too Much Xor (TOOXOR) solution in C++ | AskTheCode
Problem:
Chef calls a sequence of integers A1,A2,…,ANgood if it satisfies the following
conditions:
In particular, any sequence with length 1 is good and any sequence of length 2
which satisfies the first condition is good.
Here, ⊕ denotes the bitwise XOR operation.
Chef gives you a sequence A1,A2,…,AN. You may perform the following operation on the sequence any number of times (possibly 0): choose 3 pairwise distinct valid indices a, b and c and change Ac to Aa⊕Ab. Note that this means the operation can only be performed if N≥3.
Chef is asking you to make the sequence good using at most 3⋅N operations or report that it is impossible. Note that you do not have to minimise the number of performed operations.
Input:
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output:
For each test case:
If it is impossible to change the given sequence into a good sequence using at most 3⋅N operations, print a single line containing the integer −1.
Otherwise, first, print a line containing a single integer M (0≤M≤3⋅N) ― the number of operations you want to perform.
Then, print M lines describing these operations in the order in which you want to perform them. For each i (1≤i≤M), the i-th of these lines should contain three space-separated integers ai, bi and ci (pairwise distinct; 1≤ai,bi,ci≤N) ― the indices on which the i-th operation is performed.
If there are multiple solutions, you may find any one of them.
Sample Input:
4
1
69
3
1 2 3
3
1 3 1
2
10 10Sample Output:
0
-1
4
1 3 2
2 1 3
3 2 1
1 3 2
-1EXPLANATION:
Example case 1: The sequence is already good, so performing 0 operations is a valid solution.
Example case 2: The sequence cannot be made good using at most 3⋅N operations.
Example case 3: We can make the sequence good by performing the 4 operations shown on the output, in this order. Note that the initial sequence is also good, so performing 0 operations is also a valid solution.
Example case 4: The sequence does not satisfy the first condition and since N=2, we cannot perform any operations on it.
Code:
#include <bits/stdc++.h>
#define mod 1000000007
#define fain(arr) for(ll i=0;i<n;i++)cin>>arr[i];
#define all(x) x.begin(),x.end()
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bugv(n1) if(DEBUG)cout<<#n1<<" is "<<n1<<'\n';
#define buga(A) cout<<#A<<" is :"<<endl ; for(auto x:A)cout<<x<<" "; cout<<endl;
#define FILE freopen("input.txt","r",stdin);
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define endl '\n'
#define ll long long
#define pii pair<ll,ll>
#define pll pair<long long ,long long >
#define pi acos(-1)
#define sz(x) ((ll)x.size())
#define clr(x) memset(x, 0, sizeof(x))
#define init(x, a) memset(x, a, sizeof(x))
#define DEBUG true
using namespace std;
int main(){
// FILE;
SPEED;
ll t;
cin>>t;
// t=1;
while(t--)
{
ll n;
cin>>n;
ll arr[n];
fain(arr);
if(n==1){
cout<<0<<endl;
continue;
}
else if(n==2){
if((arr[0]^arr[1])!=0){
cout<<0<<endl;
}
else{
cout<<-1<<endl;
}
continue;
}
else if(n==3){
bool poss = true;
for(ll i=1;i<3;i++)
if((arr[i]^arr[i-1])==0)
poss=false;
if((arr[0]^arr[1]^arr[2])!=arr[1]){
poss=false;
}
if(poss){
cout<<0<<endl;
}
else{
vector<vector<int>> op;
for(int i=0;i<3;i++){
int brr[3];
for(int j=0;j<3;j++)brr[j]=arr[j];
ll allxor = arr[0]^arr[1]^arr[2];
brr[i]=allxor^brr[i];
bool poss = true;
for(ll pp=1;pp<3;pp++)
if((brr[pp]^brr[pp-1])==0)
poss=false;
if((brr[0]^brr[1]^brr[2])!=brr[1]){
poss=false;
}
vector<int> xxx = {0,2,1};
for(int pp=0;pp<3;pp++){
if(xxx[pp]==i){
swap(xxx[pp],xxx[2]);
break;
}
}
if(poss){
op.push_back(xxx);
break;
}
}
if(op.size()>0){
cout<<op.size()<<endl;
for(auto x:op){
cout<<x[0]+1<<" "<<x[1]+1<<" "<<x[2]+1<<endl;
}
}
else{
cout<<-1<<endl;
}
}
}
else{
if(arr[0]!=0)
{
vector<vector<ll>> op;
op.push_back({0,1,2});
op.push_back({0,1,3});
op.push_back({2,3,1});
for(ll i=2;i<n;i++){
if(i%2==0){
op.push_back({0,1,i});
}
else{
op.push_back({0,2,i});
}
}
cout<<op.size()<<endl;
for(auto x:op){
cout<<x[0]+1<<" "<<x[1]+1<<" "<<x[2]+1<<endl;
}
}
else{
vector<vector<ll>> op;
int nzi=-1;
int ii=0;
for(auto x:arr){
if(x!=0){
nzi=ii;
break;
}
ii++;
}
if(nzi==-1){
cout<<-1<<endl;
}
else{
if(nzi!=1)
op.push_back({0,nzi,1});
op.push_back({0,1,3});
op.push_back({1,3,2});
for(ll i=4;i<n;i++){
if(i%2==1){
op.push_back({0,1,i});
}
else{
op.push_back({0,2,i});
}
}
cout<<op.size()<<endl;
for(auto x:op){
cout<<x[0]+1<<" "<<x[1]+1<<" "<<x[2]+1<<endl;
}
}
}
}
}
}
Comments