6.4 VJ F - Carousel

#include<bits/stdc++.h>
#define ll long long
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const ll nl=1e18;
/*
一行数表示围成一圈的图案，他们可能相同或不同，现在要给他们上色，条件是相邻两个不同的图案颜色必须不同，求使用最少颜色的方案
通过尝试很多例子我分了四种情况，解释见代码
*/
int main()
{
    speed_up;
    int t;
    cin>>t;
    map<int,int>m;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n],s1=0,p=-1;
        m.clear();
        cin>>a[0];
        for(int i=1;i<n;i++)
        {
            cin>>a[i];
            if(a[i]==a[i-1])p=i;
            //记录了最后两个相邻且一样图案的位置，因为只需要找到一对，将他们染成同样的颜色，相当于把这两个数看作一个数，相当于奇数变偶数
            else s1=1;//判断是否全为一种颜色
        }
        if(a[0]==a[n-1])p=0;//容易忘记判断第一个和最后一个
        //1.图案全都一样，只涂一种颜色
        if(s1==0){
            cout<<1<<endl;
            for(int i=0;i<n;i++)cout<<1<<" ";
        }
        //2.图案有偶数个
        else if(n%2==0)
        {
            cout<<2<<endl;
            for(int i=0;i<n/2;i++)cout<<1<<" "<<2<<" ";
        }
        //3.图案有奇数个，分两种情况
        //第一种：所有相邻的图案都不一样
        else if(p==-1)
        {
            cout<<3<<endl;
            for(int i=0;i<n/2;i++)cout<<1<<" "<<2<<" ";
            cout<<3;
        }
        //第二种：有相邻且一样的图案，分三个部分输出（我输出的稍微麻烦了点）
        else if(p!=-1)
        {
            int r=1;
            cout<<2<<endl;
            for(int i=0;i<p;i++)
            {
                if(r==1){
                    cout<<1<<" ";
                    r=2;
                }
                else{
                    cout<<2<<" ";
                    r=1;
                }
            }
            if(r==1)
            {
                cout<<2<<" ";
                r=2;
            }
            else{
                cout<<1<<" ";
                r=1;
            }
            for(int i=p+1;i<n;i++)
            {
                if(r==1){
                    cout<<2<<" ";
                    r=2;
                }
                else
                {
                    cout<<1<<" ";
                    r=1;
                }
            }
        }
        cout<<endl;
    }
}