Submission #370167

#	Time	Username	Problem	Language	Result	Execution time	Memory
370167		stoyan_malinin	Building 4 (JOI20_building4)	C++14	0 / 100	477 ms	8812 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++)
    {
        if(maxB[i].first>=toCompensate)
        {
            ind = i;
            break;
        }
    }

    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
        {
            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;
            };

            /*
            while(toCompensate>0)
            {
                if(check(l)==true)
                {
                    toCompensate--;
                    s[l] = 1;

                    l++;
                }
                else if(check(r)==true)
                {
                    toCompensate--;
                    s[r] = 1;

                    r--;
                }
                else
                {
                    cout << 1/0 << '\n';
                }
            }
            */

            for(int iter = 0;iter<toCompensate;iter++)
            {
                for(int i = ind-maxB[ind].second+1;i<=ind;i++)
                {
                    if(check(i)==true)
                    {
                        s[i] = 1;
                        break;
                    }
                }
            }

            break;
        }
    }



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

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:140:17: warning: unused variable 'l' [-Wunused-variable]
  140 |             int l = ind - maxB[ind].second + 1;
      |                 ^
building4.cpp:141:17: warning: unused variable 'r' [-Wunused-variable]
  141 |             int r = ind;
      |                 ^

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