TOOXOR - Editorial

editorial
, , ,
15

Consider case-

1
4
0 1 1 1
2 Likes
16 
#include <bits/stdc++.h>

using namespace std;

struct tri
{
    int a; int b; int c;
};

int main()
{
   ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

   int tt;  cin>>tt;

   while(tt--)
   {
       int n;  cin>>n;

       int ar[n+1]; pair<int,int>br[n];

       for(int i=1;i<=n;i++)
          {cin>>ar[i]; br[i-1]={ar[i],i};}

           if(n==1) {cout<<0<<endl; continue;}
       if(n==2)
        { if(ar[1]==ar[2])  {cout<<-1<<endl; continue;}
       else {cout<<0<<endl; continue;}

        }

        bool bb=0;
        for(int i=1;i<=n;i++)
            {
                if(ar[i]!=0) bb=1;
            }
        if(bb==0) {cout<<-1<<endl; continue;}
        int x,y;
        sort(br,br+n);
        bool ff=1;
        for(int i=1;i<n;i++)
        {
            if(br[i].first==br[i-1].first)
            {
                ff=0;
                x=br[i].second;
                y=br[i-1].second;
                break;
            }
        }
          vector<tri>ans;
           if(ar[1]==0)
       {ar[1]=br[n-1].first^br[n-2].first;
        ans.push_back({br[n-1].second,br[n-2].second,1});
       }

        if(ff==1)
            {    if(n==3)
                {cout<<-1<<endl; continue;}
                else{
                    ar[2]=ar[1]^ar[n];
                    ans.push_back({1,n,2});
                    x=2;
                    ar[3]=ar[1]^ar[n];
                    ans.push_back({1,n,3});
                    y=3;
                }
        }









        for(int i=2;i<=n;i+=2)
        {
            if(i==x || i==y)
            {
                continue;
            }
            else{
                ar[i]=0;

                ans.push_back({x,y,i});
            }
        }
        int pos;
        for(int i=2;i<=n;i+=2 )
        {
            if(ar[i]==0)
            {
               pos=i; break;
            }
        }

       for(int i=3;i<=n;i+=2)
       {
           ar[i]=ar[1];
           ans.push_back({1,pos,i});
       }


       int pos1;

       for(int i=3;i<=n;i+=2)
       {
           if(ar[i]==ar[1]&&i!=x&& i!=y)
           {
               pos1=i; break;
           }
       }

       if(x%2==0)
       {
           ar[x]=0;
           ans.push_back({1,pos1,x});

       }

        if(y%2==0)
       {
           ar[y]=0;
           ans.push_back({1,pos1,y});

       }

       cout<<ans.size()<<endl;

       for(int i=0;i<ans.size();i++)
        cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<endl;
   }
    return 0;
}

please anybody tell why this code isn’t working

17

Looks like some undefined behavior on

1
3
1 1 1
18

Ya, my code fails on this test case! Thanks for highlighting it.
I corrected my code and it gave AC finally :slight_smile:
Thanks a lot! Feeling a lot relieved!

1 Like
19

@akshitm16 can you please check this code?
https://www.codechef.com/viewsolution/48057380

20

Consider case-

1
4
0 0 0 1
21

My Output :
4
1 4 2
1 4 4
2 4 1
2 4 3

Final sequence according to this:
0 1 0 1

22

choose 3 pairwise distinct valid indices a, b and c.

23

https://www.codechef.com/viewsolution/48073510
Can somebody help me out to find the testcase were it is failing

24

Consider case-

1
3
0 0 1
25

if n = 3
array is : 1 2 3
answer is -1
but if i choose i = 1, j = 3, k = 2. so arr[k] = arr[i] ^ arr[j]
array become : 1 (1^3) 3
again i choose i = 1, j = 3, k = 2. so arr[k] = arr[i] ^ arr[j]
array become 1 (1^3^1^3) 3 = 1 0 3
and i choose i = 2, j = 3, k = 1. so arr[k] = arr[i] ^ arr[j]
array become 3 0 3.
This is a good array So why the output is -1 for this.
Please Correct me if I wrongly understand the problem.???

26

Operation is A_k=A_i\oplus A_j you’ve done A_k=A_k \oplus A_i \oplus A_j

2 Likes
27

yeah I forget😅 thanks for the clarification

28

Can anyone tell what is the mistake in my code.

29

Can you post the link instead?

30

Yup ,too many edge cases to handle in a short contest … Could have appeared in long

31

ok

32

Consider case-

1
3
0 0 1
33

after considering this case still answer is wrong

34

Your new solution fails for this-

1
3
1 1 1

I’ll add more in some time.

Edit:
Consider this as well

1
4
0 0 0 1