Submission #877381

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

building4

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 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 bl = 0;
    for (int i = 0; i < b.size(); i ++)
    {
        if (b[i] == 'A')
            bl ++;
        else
            bl --;
    }

    assert(balance % 2 == 0 && bl % 2 == 0);

    if (balance < 0 && bl < 0)
        assert(false);

    ///int lf = 0, rf = (int)(a.size()) - 1;
    while(balance != 0)
    {
        bool tf = false;
        for (int i = 0; i < n && balance != 0; i ++)
        {
            tf = max(tf, can_swap(a, balance, i));
        }
        if (!tf)
            break;
    }



    if (balance != 0)
        cout << -1 << endl;
    else
    {
        /**assert(n == a.size());
        int cnt = 0, cnt2 = 0;
        for (int i = 0; i < n; i ++)
            if (a[i] == 'A')
                cnt ++;
            else
            if (a[i] == 'B')
                cnt2 ++;
        assert(cnt == n / 2 && cnt2 == n / 2);
        for (int i = 1; i < n; i ++)
        {
            int val = l[i][0];
            if (a[i] == 'B')
                val = l[i][1];
            int bef = l[i - 1][0];
            if (a[i - 1] == 'B')
                bef = l[i - 1][1];
            assert(bef <= val);
        }*/
        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:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < b.size(); i ++)
      |                     ~~^~~~~~~~~~

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