Submission #370769

#	Time	Username	Problem	Language	Result	Execution time	Memory
370769		stoyan_malinin	Building 4 (JOI20_building4)	C++14	100 / 100	1287 ms	181292 KiB

building4

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

using namespace std;

const int MAXN = 1e6 + 1e5 + 5;

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

map <int, set <pair <int, int>>> chainVals;

vector <int> getGreedy()
{
    int lastVal = -1;
    vector <int> v;

    for(int i = 0;i<n;i++)
    {
        int smallInd = 0, bigInd = 1;
        if(a[i][smallInd]>a[i][bigInd]) swap(smallInd, bigInd);

        if(lastVal<=a[i][smallInd])
        {
            v.push_back(smallInd);
            lastVal = a[i][smallInd];
        }
        else if(lastVal<=a[i][bigInd])
        {
            v.push_back(bigInd);
            lastVal = a[i][bigInd];
        }
        else
        {
            return {};
        }
    }

    return v;
}

int netChange[MAXN], chain[MAXN];

void doFlip(int i, vector <int> &s)
{
    if(i==n) return;

    s[i] ^= 1;
    if(i!=n-1 && a[i][s[i]]>a[i+1][s[i+1]]) doFlip(i+1, s);
}

bool checkSol(vector <int> &s)
{
    int lastVal = -1;
    for(int i = 0;i<n;i++)
    {
        if(lastVal>a[i][s[i]]) return false;
        lastVal = a[i][s[i]];
    }

    return true;
}

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

    vector <int> s = getGreedy();
    if(s.empty()==true)
    {
        cout << "-1" << '\n';
        return 0;
    }

    int aCnt = 0;
    for(int x: s) aCnt += (x==0);

    for(int i = n-1;i>=0;i--)
    {
        if((i==0 || a[i-1][s[i-1]]<=a[i][s[i]^1]) && (i==n-1 || a[i][s[i]^1]<=a[i+1][s[i+1]]))
        {
            netChange[i] = ((s[i]==0)?-1:+1);
            chain[i] = i;
        }
        else if((i==0 || a[i-1][s[i-1]]<=a[i][s[i]^1]) && (i==n-1 || a[i][s[i]^1]<=a[i+1][s[i+1]^1]) && chain[i+1]!=-1)
        {
            netChange[i] = ((s[i]==0)?-1:+1) + netChange[i+1];
            chain[i] = chain[i+1];
        }
        else
        {
            netChange[i] = 0;
            chain[i] = -1;
        }
    }

    /*
    cout << '\n';

    for(int i = 0;i<n;i++) cout << s[i] << " ";
    cout << '\n';

    for(int i = 0;i<n;i++) cout << netChange[i] << " ";
    cout << '\n';

    for(int i = 0;i<n;i++) cout << chain[i] << " ";
    cout << '\n';
    */

    for(int i = 0;i<n;i++)
    {
        if(chain[i]!=-1) chainVals[chain[i]].insert({netChange[i], i});
    }

    for(auto &item: chainVals)
    {
        if(aCnt>n/2)
        {
            auto it = item.second.begin();
            while(it!=item.second.end())
            {
                //cout << "k" << '\n';
                if(it->first<0 && aCnt + it->first >= n/2)
                {
                    aCnt += it->first;
                    doFlip(it->second, s);

                    //cout << " -> flip: " << it->second << '\n';
                    break;
                }

                it++;
            }
        }
        else if(aCnt<n/2)
        {
            auto it = prev(item.second.end());
            while(true)
            {
                if(it->first>0 && aCnt + it->first <= n/2)
                {

                    aCnt += it->first;
                    doFlip(it->second, s);

                    //cout << " -> flip: " << it->second << '\n';
                    break;
                }

                if(it==item.second.begin()) break;
                it--;
            }
        }
    }

    if(checkSol(s)==false || aCnt!=n/2)
    {
        cout << "-1" << '\n';
    }
    else
    {
        for(int x: s) cout << char('A'+x);
        cout << '\n';
    }
}

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