Submission #370237

#	Time	Username	Problem	Language	Result	Execution time	Memory
370237		stoyan_malinin	Building 4 (JOI20_building4)	C++14	11 / 100	406 ms	99420 KiB

building4

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

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;
        if(memo[ind][lastChoice]!=-1)
            return memo[ind][lastChoice];

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

        memo[ind][lastChoice] = ans;
        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;
    }
}

int comp[MAXN];
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;
        }
    }

    comp[0] = 0;
    for(int i = 1;i<n;i++)
    {
        if(a[i-1][1]<=a[i][1]) comp[i] = comp[i-1];
        else comp[i] = i;
    }

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

    int lastB = -1;
    deque <int> dq;

    for(int i = 0;i<n;i++)
    {
        if(s[i]==1) lastB = i;

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

        while(dq.empty()==false && (dq.back()<=lastB || comp[dq.back()]!=comp[i]))
                dq.pop_back();

        if(s[i]==0 && (i==0 || a[i-1][s[i-1]]<=a[i][1]))
        {
            while(dq.empty()==false)
            {
                int val1 = ((dq.front()-2>=0)?maxB[dq.front()-2].first:0) + (i-dq.front()+1);
                int val2 = ((i-2>=0)?maxB[i-2].first:0) + (i-i+1);

                if(val1<val2) dq.pop_front();
                else break;
            }

            dq.push_front(i);
        }

        if(i==n-1 || a[i][1]<=a[i+1][s[i+1]])
        {
            if(dq.empty()==false)
            {
                int j = dq.back();

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

            for(int j = 0;j<=min(2, i);j++)
            {
                if(j<=lastB) continue;
                if(j!=i && comp[i]!=comp[j]) continue;

                if(j==0 || a[j-1][s[j-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)));
                }
            }
        }

        //cout << maxB[i].first << " " << maxB[i].second << '\n';
    }

    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(ind<0)
        {
            cout << 1/0 << '\n';
            return 0;
        }

        if(maxB[ind].second<=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;

            bool found = 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;
                            }

                            found = true;
                            break;
                        }
                    }
                }

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

                            found = true;
                            break;
                        }
                    }
                }
            }

            if(found==false)
            {
                cout << 1/0 << '\n';
            }

            break;
        }
    }


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

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:179:22: warning: division by zero [-Wdiv-by-zero]
  179 |             cout << 1/0 << '\n';
      |                     ~^~
building4.cpp:238:26: warning: division by zero [-Wdiv-by-zero]
  238 |                 cout << 1/0 << '\n';
      |                         ~^~

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