Submission #877350

#	Time	Username	Problem	Language	Result	Execution time	Memory
877350		danikoynov	Building 4 (JOI20_building4)	C++14	0 / 100	3 ms	4612 KiB

building4

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;

int n, l[maxn][2];
void input()
{
    cin >> n;
    n *= 2;
    for (int i = 1; i <= n; i ++)
        cin >> l[i][0];
    for (int i = 1; i <= n; i ++)
        cin >> l[i][1];
}


int dp[maxn][2], from[maxn][2];
string get_max(int c)
{
    for (int i = 1; i <= n; i ++)
    {
        dp[i][0] = dp[i][1] = -1e9;
        from[i][0] = from[i][1] = -1;
    }

    dp[1][c] = 1;
    dp[1][(1 + c) % 2] = 0;

    ///cout << "--------------" << endl;
    for (int i = 2; i <= n; i ++)
    {
        for (int t = 0; t < 2; t ++)
            for (int d = 0; d < 2; d ++)
            {
                if (l[i - 1][t] <= l[i][d])
                {
                    int val = dp[i - 1][t] + (d == c);
                    if (val > dp[i][d])
                    {
                        from[i][d] = t;
                        dp[i][d] = val;
                    }
                }
            }

        ///cout << dp[i][0] << " " << dp[i][1] << endl;
    }

    string res = "";
    if (dp[n][0] < 0 && dp[n][1] < 0)
        return res;

    int row = n, state = 0;
    if (dp[n][1] > dp[n][0])
        state = 1;


    while(row > 1)
    {
        ///cout << state << endl;
        if (state == 0)
            res.push_back('A');
        else
            res.push_back('B');

        state = from[row][state];
        row --;
    }

    if (state == 0)
        res.push_back('A');
    else
        res.push_back('B');

    reverse(res.begin(), res.end());
    return res;
}

bool can_swap(string &a, int &b, int pos)
{


    int val = l[pos][0];
    if (a[pos] == 'A')
        val = l[pos][1];
    if (pos > 0)
    {
        int bef = l[pos - 1][0];
        if (a[pos - 1] == 'B')
            bef = l[pos - 1][1];
        if (bef > val)
            return false;
    }

    if (pos + 1 < a.size())
    {
        int nxt = l[pos + 1][0];
        if (a[pos + 1] == 'B')
            nxt = l[pos + 1][1];
        if (nxt < val)
            return false;
    }


    if (a[pos] == 'A')
    {
        a[pos] = 'B';
        b -= 2;
    }
    else
    {
        a[pos] = 'A';
        b += 2;
    }

    return true;
}
void simulate()
{
    string a = get_max(0);
    string b = get_max(1);

    if (a.empty() || b.empty())
    {
        cout << -1 << endl;
        return;
    }


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

    int lf = 0, rf = (int)(a.size()) - 1;
    while(balance > 0)
    {
        while(lf < a.size() && a[lf] == b[lf])
            lf ++;
        while(rf >= 0 && a[rf] == b[rf])
            rf --;

        if (lf > rf)
            break;

        if (can_swap(a, balance, lf))
        {
            lf ++;
            continue;
        }

        if (can_swap(a, balance, rf))
        {
            rf --;
            continue;
        }

        break;
    }

    if (balance != 0)
        cout << -1 << endl;
    else
        cout << a << endl;
}
void solve()
{
    input();
    simulate();
}
int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'bool can_swap(std::string&, int&, int)':
building4.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     if (pos + 1 < a.size())
      |         ~~~~~~~~^~~~~~~~~~
building4.cpp: In function 'void simulate()':
building4.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0; i < a.size(); i ++)
      |                     ~~^~~~~~~~~~
building4.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while(lf < a.size() && a[lf] == b[lf])
      |               ~~~^~~~~~~~~~

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