T429423 「LAOI-4」Mex Tower (Easy ver.)

/*
	手玩数据找规律
	你会发现有很强的规律性
*/
// O(n)
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;
string s;
int x[3] = {2, 1, 0};
int y[3] = {2, 0, 1};
int x2[3] = {1, 0, 2};
int y2[3] = {0, 1, 2};

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        s.clear();
        if (n == 1) cout << '2';
        else if (n == 2) cout << "0 1";
        else 
        {
            if ((n & 1) == 0)
            {
                n -= 2;
                string s2, s3;
                for (int i = 0; i < n; i += 2)
                {
                    s2 += x[i % 3] + '0';
                    s3 += y[i % 3] + '0';
                }
                reverse(s2.begin(), s2.end());
                s += s2;
                s += "01";
                s += s3;
            }
            else 
            {
                n -- ;
                n /= 2;
                string s2, s3;
                for (int i = 0; i < n; i ++ )
                {
                    s2 += x2[i % 3] + '0';
                    s3 += y2[i % 3] + '0';
                }
                // cout << s2 << endl;
                reverse(s2.begin(), s2.end());
                // cout << s2 << s3 << endl;
                s += s2;
                s += "2";
                s += s3;
            }
            for (int i = 0; s[i]; i ++ ) cout << s[i] << ' ';
        }
        
        puts("");
    }
    
    return 0;
}

/*
// O(n^2)
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int n, m;
string s;

char get(char a, char b)
{
    int sum = 0;
    if (a == '0' || b == '0') sum ++ ;
    if (sum == 1 && (a == '1' || b == '1')) sum ++ ;
    return sum + '0';
}

string make(string s1)
{
    string s2, s3;
    if (s1.compare("2") == 0) return (string)"01";
    int len = s1.size() - 1;
    for (int i = 0; i < len; i ++ )
    {
        s2 += get(s1[i], s1[i + 1]);
    }
    s3 += get(s1[0], s2[0]);
    s3 += s2;
    s3 += get(s2[len - 1], s1[len]);
    return s3;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        s.clear();
        if (n == 1) cout << '2';
        else if (n == 2) cout << "0 1";
        else 
        {
            s = "01";
            n -= 2;
            while (n -- ) s = make(s);
            for (int i = 0; s[i]; i ++ ) cout << s[i] << ' ' ;
        }
        puts("");
    }
    
    return 0;
}
*/