Submission #1234086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234086		vicvic	Cheerleaders (info1cup20_cheerleaders)	C++20	100 / 100	457 ms	20972 KiB

cheerleaders

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX=(1 << 17);
int n;
vector <int> a, poz;
vector <int> xored (int x)
{
    vector <int> ret;
    for (int bit=0;bit<n;bit++)
    {
        ret.push_back (1);
        if (x & (1 << bit))
            ret.push_back (0);
    }
    return ret;
}
void fct (vector <int> &v, int type)
{
    if (type==0)
    {
        for (int i=0;i<(1 << n);i++)
            v[i]^=(1 << (n-1));
    }
    else
    {
        for (int i=0;i<v.size();i++)
        {
            if (v[i]%2)
                v[i]=v[i]/2+(1 << (n-1));
            else
                v[i]/=2;
        }
    }
}
int32_t main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    a.resize (1 << n);
    poz.resize (1 << n);
    for (int i=0;i<(1 << n);i++)
        cin >> a[i], poz[a[i]]=i;
    int ans=1e18;
    vector <int> op;
    fct (poz, 1);
    for (int i=0;i<n;i++)
    {
        vector <vector <int>> before (n, vector <int> ((1 << n), 0));
        vector <vector <int>> p (n, vector <int> (2, 0));
        for (int j=0;j<(1 << n);j++)
        {
            int val=0;
            for (int bit=n-1;bit>=0;bit--)
            {
                if (poz[j]& (1 << bit))
                {
                    p[bit][1]+=before[bit][val];
                    val+=(1 << bit);
                }
                else
                {
                    p[bit][0]+=before[bit][val+(1 << bit)];
                }
                before[bit][val]++;
            }
        }
        int sum=0, x=0;
        for (int j=0;j<n;j++)
        {
            if (p[j][1]<p[j][0])
                x^=(1 << j);
            sum+=min (p[j][1], p[j][0]);
        }
        if (sum<ans)
        {
            ans=sum;
            vector <int> crt=xored (x);
            op.clear ();
            for (int j=0;j<=i;j++)
                op.push_back (1);
            for (auto chestie : crt)
                op.push_back (chestie);
        }
        fct (poz, 1);
    }
    if (n==0)
        ans=0;
    cout << ans << "\n";
    for (auto chestie : op)
        cout << (chestie==0?1:2);
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28