Submission #370283

#	Time	Username	Problem	Language	Result	Execution time	Memory
370283		stoyan_malinin	Building 4 (JOI20_building4)	C++14	11 / 100	568 ms	194232 KiB

building4

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

using namespace std;

const int MAXN = 1e6 + 1e5 + 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*2;
        int lastVal = ((ind==0)?-1:a[ind-1][lastChoice]);

        for(int c = 1;c>=0;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;

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

        for(int i = 0;i<n;i++)
        {
            for(int c = 1;c>=0;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];

vector <int> bOccurences;

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) bOccurences.push_back(i);

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

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

        if((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);

                val1 -= bOccurences.end() - lower_bound(bOccurences.begin(), bOccurences.end(), dq.front());
                val2 -= bOccurences.end() - lower_bound(bOccurences.begin(), bOccurences.end(), i);

                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)
            {
                auto it = prev(dq.end());
                for(int iter = 0;iter<min(5, (int)dq.size());iter++)
                {
                    int j = *it;it--;
                    int val = ((j-2>=0)?maxB[j-2].first:0);
                    val -= bOccurences.end() - lower_bound(bOccurences.begin(), bOccurences.end(), j);

                    maxB[i] = max(maxB[i], make_pair(val+(i-j+1), (i-j+1)));
                }
                //int j = dq.back();


            }

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

            for(int j = max(0, i-369);j<=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)
    {
        if(n>4000) cout << 1/0 << '\n';

        cout << "-1" << '\n';
        return 0;
    }

    while(toCompensate>0)
    {
        if(ind<0)
        {
            cout << 1/0 << '\n';
            return 0;
        }

        int cnt = 0;
        for(int i = ind-maxB[ind].second+1;i<=ind;i++)
            if(s[i]==0) cnt++;

        if(cnt<=toCompensate)
        {
            toCompensate -= cnt;
            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)
                        {
                            int cnt = 0;
                            for(int j = l;j<=i;j++)
                                if(s[j]==0) cnt++;

                            if(cnt==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)
                        {
                            int cnt = 0;
                            for(int j = i;j<=r;j++)
                                if(s[j]==0) cnt++;

                            if(cnt==toCompensate)
                            {
                                for(int j = i;j<=r;j++)
                                {
                                    s[j] = 1;
                                }

                                found = true;
                                break;
                            }
                        }
                    }
                }
            }

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

            break;
        }
    }

    int lastVal = -1;
    if(s.size()!=n)
    {
        cout << 1/0 << '\n';
    }

    int balance = 0;
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]==0) balance += 1;
        else balance += -1;
    }

    if(balance!=0)
    {
        cout << 1/0 << '\n';
    }

    for(int i = 0;i<s.size();i++)
    {
        if(lastVal>a[i][s[i]])
        {
            cout << 1/0 << '\n';
            return 0;
        }

        lastVal = a[i][s[i]];
    }

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


}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:204:29: warning: division by zero [-Wdiv-by-zero]
  204 |         if(n>4000) cout << 1/0 << '\n';
      |                            ~^~
building4.cpp:214:22: warning: division by zero [-Wdiv-by-zero]
  214 |             cout << 1/0 << '\n';
      |                     ~^~
building4.cpp:291:26: warning: division by zero [-Wdiv-by-zero]
  291 |                 cout << 1/0 << '\n';
      |                         ~^~
building4.cpp:299:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  299 |     if(s.size()!=n)
      |        ~~~~~~~~^~~
building4.cpp:301:18: warning: division by zero [-Wdiv-by-zero]
  301 |         cout << 1/0 << '\n';
      |                 ~^~
building4.cpp:305:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |     for(int i = 0;i<s.size();i++)
      |                   ~^~~~~~~~~
building4.cpp:313:18: warning: division by zero [-Wdiv-by-zero]
  313 |         cout << 1/0 << '\n';
      |                 ~^~
building4.cpp:316:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  316 |     for(int i = 0;i<s.size();i++)
      |                   ~^~~~~~~~~
building4.cpp:320:22: warning: division by zero [-Wdiv-by-zero]
  320 |             cout << 1/0 << '\n';
      |                     ~^~
building4.cpp:109:9: warning: unused variable 'lastB' [-Wunused-variable]
  109 |     int lastB = -1;
      |         ^~~~~

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