COMPETITIVE-PROGRAMMING/LTIME52_2.cpp at master · govind1996/COMPETITIVE-PROGRAMMING · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
int a[6][6];
bool mark[6]={0};
int cnt=0;
using namespace std;
int solve(int s)
{
    if(cnt==6)
        return 1;
    for(int i=0;i<6;i++)
    {
        if(a[s][i]==1)
        {
            cnt+=2;
            for(int j=0;j<6;j++)
                {

                    if(a[j][i])
                        a[j][i]=2;
                    if(a[j][s])
                        a[j][s]=2;
                }
            a[s][i]=1;
            a[i][s]=1;
            mark[s]=1;
            mark[i]=1;
            int k=-1,l=0;
            while(mark[l]&&l<6)
                l++;
            k=l;
            if(k!=6)
            {
                if(solve(k))
                    return 1;
                else
                {
                    cnt-=2;
                    for(int j=0;j<6;j++)
                       {
                         if(a[j][i]==2)
                            a[j][i]=1;
                         if(a[j][i]==2)
                         a[j][s]=1;
                       }
                    a[s][i]=0;
                    a[i][s]=0;
                    mark[s]=0;
                    mark[i]=0;
                }
            }
            else
                return 1;
        }
    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,flag=1,o=0;
        for(int i=0;i<6;i++)
            mark[i]=0;
        cnt=0;
        cin>>n;
        for(int i=0;i<6;i++)
        {
            for(int j=0;j<6;j++)
            {
                if(i==j)
                    a[i][j]=0;
                else
                    a[i][j]=1;
            }
        }
        int x;
        cin>>x;
        for(int i=1;i<n;i++)
        {
            int y;
            cin>>y;
            if(x==y)
            flag=0;
            a[x-1][y-1]=0;
            a[y-1][x-1]=0;
            x=y;

        }
        if(flag==0)
            cout<<"-1"<<endl;
        else if(n!=1)
        {
            if(solve(0))
                {
                    for(int i=0;i<6;i++)
                    {
                        for(int j=0;j<6;j++)
                        {
                            if(a[i][j]==1&&o<=6)
                                {
                                    cout<<j+1<<" ";
                                    o++;
                                }
                        }
                    }
                    cout<<endl;
                }
                else
                    cout<<"-1"<<endl;
        }
        else
        {
            cout<<"2 1 4 3 6 5"<<endl;
        }
    }
}