[Êý¾Ý½á¹¹ÓëËã·¨]P7939 [B1] Alice Wins (easy version)--Ìâ½â±¨¸æ

퉀
ÌâÄ¿ÃèÊö

The difference between the versions is the limit of operations.

Alice is a cute girl who has a lot of dolls.

There are?4\cdot n4?n?dolls playing?rock-paper-scissors. They are divided into two teams: Team A and Team B. Each team contains?2\cdot n2?n?dolls.

A total of?2\cdot n2?n?rounds of the game will be played. In the?ii-th round, the?ii-th doll in Team A will play against the?ii-th doll in Team B. If the doll in Team A wins, Team A will get?11?point. If it loses, Team A will lose?11?point. If it ties, Team A will not get points.

Alice knows all the dolls' choices in this game. To be precise, she uses two arrays?aa?and?bb?to represent the choices of the dolls in the two teams.?a_iai??means the choice of the?ii-th doll in Team A, and?b_ibi??means the choice of the?ii-th doll in Team B. In this question, we use?11?for rock,?22?for scissors, and?33?for paper.

Now for?each team, Alice wants to change the choices of?at most?nn?dolls to make the score of Team A as high as possible.

Find the maximum score of Team A and its construction method. If there are multiple answers print any of them (you still have to maximize the score of Team A).

ÊäÈë¸ñʽ

Each test contains multiple testcases. The first line contains an integer?TT, the number of test cases.

For each test case, the first line contains one integer?nn.

Then two lines follow, containing an array?aa?of length?2\cdot n2?n?and an array?bb?of length?2\cdot n2?n, respectively.

Êä³ö¸ñʽ

For each test case, print three lines.

The first line contains one integer, the maximum score of Team A.

The second line contains an array?a'a¡ä?of length?2\cdot n2?n, which represents the?aa?array after Alice's modification. For integers?11?to?2\cdot n2?n, if?a_i \ne a'_iai?ªÁ=ai¡ä?, then it means you have modified the choice of one player in Team A.

The third line contains an array?b'b¡ä?of length?2\cdot n2?n, which represents the?bb?array after Alice's modification. For integers?11?to?2\cdot n2?n, if?b_i \ne b'_ibi?ªÁ=bi¡ä?, then it means you have modified the choice of one player in Team B.

ÌâÒâ·­Òë

AB ÿ¶Ó?2n2n?ÈËÕýÔÚÍæʯͷ¼ôµ¶²¼¡£A ¶ÓµÚ?ii?¸öÈ˳ö?a_iai?，B ¶ÓµÚ?ii?¸öÈ˳ö?b_ibi?¡£±àºÅÏàͬµÄÈË»á¶ÔÕ½¡£Èô A ¶ÓÓ®Ôò¼ÓÒ»·Ö，ƽ²»µÃ·Ö，Êä¿ÛÒ»·Ö¡£Äã¿ÉÒÔÖÁ¶à¸Ä±äÿ¶Ó?nn?¸öÈ˵ijöÈ­·½°¸，ʹµÃ A ¶ÓµÄµÃ·Ö×î¸ß¡£Êä³öµÃ·ÖµÄ×î´óÖµºÍÈÎÒâÒ»×é¹¹Ôì·½°¸¡£

±¾ÌâÖÐ，ÎÒÃÇÓÃ?11?´ú±íʯͷ，22?´ú±í¼ôµ¶，33?´ú±í²¼¡£

ÊäÈëÊä³öÑùÀý

ÊäÈë #1¸´ÖÆ

2
1
1 2
1 2
2
2 3 1 3
1 2 2 1

Êä³ö #1¸´ÖÆ

2
1 1
2 2
4
3 1 1 3
1 2 2 1

˵Ã÷/Ìáʾ

Explanation

For the first test case, we can change?a_2a2??to?11?and?b_1b1??to?22. Then Team A can get?22?points. It can be proved that this is the maximum score that Team A can get.

For the second test case, we can change?a_1a1??to?33?and?a_2a2??to?11.

Constraints

1\le T,n \le 10^5;\ 1\le a_i,b_i \le 31¡ÜT,n¡Ü105;?1¡Üai?,bi?¡Ü3. The sum of?nn?over all test cases?\le 10^5¡Ü105.

½âÌâ˼·

ÆäʵÕâÌâA¶Ó¾ÍÊÇÈ«Ó®

Ç°n¸öÔªËØÐÞ¸ÄA¶Ó，ÈÃAÓ®

ºón¸öÔªËØÐÞ¸ÄB¶Ó，ÈÃAÓ®

Ó®µÄ·ÖÊý¾ÍÊÇ2*n；

´úÂëչʾ

#include<stdio.h>
int t,n,sum;
int a[1000010],b[1000010];
void fun()
{
    for(int i=1; i<=n; i++)
    {
        if(b[i]==1)
            a[i]=3;
        else if(b[i]==2)
            a[i]=1;
        else a[i]=2;
    }
    for(int i=n+1; i<=2*n; i++)
    {
        if(a[i]==1)
            b[i]=2;
        else if(a[i]==2)
            b[i]=3;
        else b[i]=1;
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        scanf("%d",&n);
        sum=2*n;//AÈ«Ó®
        for(int i=1; i<=2*n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=2*n; i++)
            scanf("%d",&b[i]);
        fun();
        printf("%d\n",sum);
        for(int i=1; i<=2*n; i++)
            printf("%d ",a[i]);
        printf("\n");
        for(int i=1; i<=2*n; i++)
            printf("%d ",b[i]);
        printf("\n");
    }
    return 0;
}