Submission #370180

#	Time	Username	Problem	Language	Result	Execution time	Memory
370180		stoyan_malinin	Building 4 (JOI20_building4)	C++14	0 / 100	471 ms	8428 KiB

building4

#include <functional>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 1e6 + 5;

int n;
int a[MAXN][2];

namespace MaxA
{
    int memo[MAXN][2];

    int rec(int ind, int lastChoice)
    {
        if(ind==n) return 0;

        int ans = -MAXN;
        int lastVal = ((ind==0)?-1:a[ind-1][lastChoice]);

        for(int c = 0;c<2;c++)
        {
            if(lastVal<=a[ind][c])
                ans = max(ans, (c==0) + rec(ind+1, c));
        }

        return ans;
    }

    vector <int> solve()
    {
        memset(memo, -1, sizeof(memo));

        vector <int> ans = {};
        int aCnt = rec(0, 0), lastVal = -1;

        for(int i = 0;i<n;i++)
        {
            for(int c = 0;c<2;c++)
            {
                if(lastVal<=a[i][c] && (c==0) + rec(i+1, c)==aCnt)
                {
                    ans.push_back(c);
                    aCnt -= (c==0);

                    lastVal = a[i][c];
                    break;
                }
            }
        }

        return ans;
    }
}

pair <int, int> maxB[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;n *= 2;
    for(int i = 0;i<n;i++) cin >> a[i][0];
    for(int i = 0;i<n;i++) cin >> a[i][1];

    for(int i = 0;i<n-1;i++)
    {
        if(min(a[i][0], a[i][1])>max(a[i+1][0], a[i+1][1]))
        {
            cout << "-1" << '\n';
            return 0;
        }
    }

    int aCnt = 0;
    vector <int> s = MaxA::solve();
    for(int i = 0;i<n;i++) aCnt += (s[i]==0);

    if(aCnt<n/2)
    {
        cout << "-1" << '\n';
        return 0;
    }

    for(int i = 0;i<n;i++)
    {
        maxB[i] = {0, 0};
        if(i!=0) maxB[i] = max(maxB[i], make_pair(maxB[i-1].first, 0));

        if(i==n-1 || a[i][1]<=a[i+1][s[i+1]])
        {
            for(int j = i;j>=0;j--)
            {
                if(s[j]==1) break;
                if(j!=i && a[j][1]>a[j+1][1]) break;

                if(j==0 || a[j-1][s[i-1]]<=a[j][1])
                {
                    int val = ((j-2>=0)?maxB[j-2].first:0);
                    maxB[i] = max(maxB[i], make_pair(val+(i-j+1), (i-j+1)));
                }
            }
        }
    }

    int ind = -1;
    int toCompensate = aCnt - n/2;

    for(int i = 0;i<n;i++)
    {
        //cout << maxB[i].first << " " << maxB[i].second << '\n';

        if(maxB[i].first>=toCompensate)
        {
            //ind = i;
            //break;
        }
    }
    if(maxB[n-1].first>=toCompensate) ind = n - 1;

    if(ind==-1)
    {
        cout << "-1" << '\n';
        return 0;
    }

    while(toCompensate!=0)
    {
        if(maxB[ind].first<=toCompensate)
        {
            toCompensate -= maxB[ind].second;
            for(int i = ind-maxB[ind].second+1;i<=ind;i++)
                s[i] = 1;

            ind = ind - maxB[ind].second - 1;
        }
        else
        {
            //cout << "OK " << ind << '\n';

            int l = ind - maxB[ind].second + 1;
            int r = ind;

            function <bool(int)> check = [&](int i)
            {
                if(s[i]==1) return false;

                if(i==0 || a[i-1][s[i-1]]<=a[i][1])
                {
                    if(i==n-1 || a[i][1]<=a[i+1][s[i+1]])
                    {
                        return true;
                    }
                }

                return false;
            };

            for(int i = l;i<=r;i++)
            {
                if(l==0 || a[l-1][s[l-1]]<=a[l][1])
                {
                    if(i==n-1 || a[i][1]<=a[i+1][s[i+1]])
                    {
                        if(i-l+1==toCompensate)
                        {
                            for(int j = l;j<=i;j++)
                            {
                                s[j] = 1;
                            }

                            goto EndCycle;
                        }
                    }
                }

                if(r==n-1 || a[r][1]<=a[r+1][s[r+1]])
                {
                    if(i==0 || a[l-1][s[l-1]]<=a[l][1])
                    {
                        if(r-i+1==toCompensate)
                        {
                            for(int j = i;j<=r;j++)
                            {
                                s[j] = 1;
                            }

                            goto EndCycle;
                        }
                    }
                }
            }

            EndCycle:
                break;
        }
    }


    for(int x: s) cout << char('A'+x);
    cout << '\n';
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 89