CHIA_RUONG

mail@pastecode.io avatar
unknown
c_cpp
a month ago
3.7 kB
130
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define MASK(i) (1LL << (i))
#define all(x) x.begin(), x.end()
const long long inf = 1e18;
const int MAXN = 1e6 + 5;
const int mod = 1e9 + 7;
void ckmin(int& f, int s)
{
    f = (f < s ? f : s);
}
void ckmax(int& f, int s)
{
    f = (f > s ? f : s);
}
const int N = 20;
const long long base = 2e5;
int z[N], n, n1, n2, sum, k, a, b, c, cnt = 0, id = 0;
long long mask, p[N], ans[MAXN], f[MAXN], s[MAXN], ord[MAXN];
void f1(int pos)
{
    if (pos == n)
    {
        f[id] = a + b * base + c * base * base;
        s[id] = mask;
        ord[id] = id;
        id++;
        return;
    }
    if (sum / 3 >= a + z[pos])
    {
        a += z[pos];
        f1(pos + 1);
        a -= z[pos];
    }
    if (sum / 3 >= b + z[pos])
    {
        b += z[pos];
        mask += p[n - pos + n1 - 1];
        f1(pos + 1);
        b -= z[pos];
        mask -= p[n - pos + n1 - 1];
    }
    if (sum / 3 >= c + z[pos])
    {
        c += z[pos];
        mask += 2 * p[n - pos + n1 - 1];
        f1(pos + 1);
        c -= z[pos];
        mask -= 2 * p[n - pos + n1 - 1];
    }
}
void f2(int pos)
{
    if (pos == n1)
    {
        long long mp = k - a + (k - b) * base + (k - c) * base * base;
        int l, r;
        {
            int low = -1, high = id;
            while (high - low > 1)
            {
                int mid = (low + high) >> 1;
                if (f[ord[mid]] >= mp) high = mid;
                else low = mid;
            }
            if (high == id || f[ord[high]] != mp) return;
            l = high;
        }
        {
            int low = -1, high = id;
            while (high - low > 1)
            {
                int mid = (low + high) >> 1;
                if (f[ord[mid]] <= mp) low = mid;
                else high = mid;
            }
            r = low;
        }
        while (l <= r)
        {
            ans[cnt++] = mask + s[ord[l]];
            l++;
        }
        return;
    }
    if (sum / 3 >= a + z[pos])
    {
        a += z[pos];
        f2(pos + 1);
        a -= z[pos];
    }
    if (sum / 3 >= b + z[pos])
    {
        b += z[pos];
        mask += p[pos];
        f2(pos + 1);
        b -= z[pos];
        mask -= p[pos];
    }
    if (sum / 3 >= c + z[pos])
    {
        c += z[pos];
        mask += 2 * p[pos];
        f2(pos + 1);
        c -= z[pos];
        mask -= 2 * p[pos];
    }
}
string st;
void solve()
{
    p[0] = 1;
    for (int i = 1; i < N; i++) p[i] = p[i - 1] * 3;
    cin >> n;
    st.resize(n);
    for (int i = 0; i < n; i++) cin >> z[i];
    sum = accumulate(z, z + n, 0);
    k = sum / 3;
    if (n < 3 || sum % 3)
    {
        cout << -1;
        return;
    }
    n1 = n >> 1;
    n2 = n - n1;
    a = b = c = mask = 0;
    f1(n1);
    sort(ord, ord + id, [&](int i, int j){
        if (f[i] == f[j]) return s[i] < s[j];
        return f[i] < f[j];
    });
    a = b = c = mask = 0;
    f2(0);
    if (!cnt) cout << -1;
    else
    {
        cout << cnt << '\n';
        for (int i = 0; i < cnt; i++)
        {
            for (int j = 0; j < n1; j++)
            {
                st[j] = (char)('A' + ans[i] % 3);
                ans[i] /= 3;
            }
            for (int j = 0; j < n2; j++)
            {
                st[n - j - 1] = (char)('A' + ans[i] % 3);
                ans[i] /= 3;
            }
            cout << st << '\n';
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}
Leave a Comment