제출 #877439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877439		danikoynov	Building 4 (JOI20_building4)	C++14	100 / 100	835 ms	83820 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;
        int val = l[row][state];
        int bef = l[row - 1][from[row][state]];
        assert(bef <= val);
        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 + 1][0];
    if (a[pos] == 'A')
        val = l[pos + 1][1];
    if (pos > 0)
    {
        int bef = l[pos][0];
        if (a[pos - 1] == 'B')
            bef = l[pos][1];
        if (bef > val)
            return false;
    }

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


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

    return true;
}

bool can_change(int pos, string &a)
{
    int val = l[pos + 1][0];
    if (a[pos] == 'A')
        val = l[pos + 1][1];

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

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

    return true;
}

set < int > act;

void check_to_change(int pos, string &a, string &b)
{
    if (pos < 0 || pos == n)
        return;

    if (a[pos] == b[pos])
        return;

    if (can_change(pos, a))
    {
        act.insert(pos);
    }
    else
    {
        if (act.find(pos) != act.end())
            act.erase(pos);
    }
}
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);

    for (int i = 0; i < n; i ++)
        check_to_change(i, a, b);
    while(balance != 0)
    {
        if (act.empty())
            break;

        int val = *act.begin();
        act.erase(val);
        assert(can_swap(a, balance, val));
        check_to_change(val - 1, a, b);
        check_to_change(val, a, b);
        check_to_change(val + 1, a, b);
    }
    ///int lf = 0, rf = (int)(a.size()) - 1;



    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 + 1][0];
            if (a[i] == 'B')
                val = l[i + 1][1];
            int bef = l[i][0];
            if (a[i - 1] == 'B')
                bef = l[i][1];
            assert(bef <= val);
        }
        cout << a << endl;
    }
}
void solve()
{
    input();
    simulate();
}
int main()
{
    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'bool can_swap(std::string&, int&, int)':
building4.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     if (pos + 1 < a.size())
      |         ~~~~~~~~^~~~~~~~~~
building4.cpp: In function 'bool can_change(int, std::string&)':
building4.cpp:143:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     if (pos + 1 < a.size())
      |         ~~~~~~~~^~~~~~~~~~
building4.cpp: In function 'void simulate()':
building4.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (int i = 0; i < a.size(); i ++)
      |                     ~~^~~~~~~~~~
building4.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for (int i = 0; i < b.size(); i ++)
      |                     ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from building4.cpp:1:
building4.cpp:229:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |         assert(n == a.size());
      |                ~~^~~~~~~~~~~

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