oj.uz

Submission #937761

# Submission time Handle Problem Language Result Execution time Memory
937761 2024-03-04T12:42:15 Z borisAngelov Building 4 (JOI20_building4) C++17
11 / 100
 41 ms 12232 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int n;

int a[maxn];
int b[maxn];

pair<int, int> dpA[maxn];
pair<int, int> dpB[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= 2 * n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= 2 * n; ++i)
    {
        cin >> b[i];
    }

    dpA[1] = make_pair(1, 1);
    dpB[1] = make_pair(0, 0);

    for (int pos = 2; pos <= 2 * n; ++pos)
    {
        dpA[pos] = make_pair(-1, -1);
        dpB[pos] = make_pair(-1, -1);

        if (a[pos] >= a[pos - 1])
        {
            if (dpA[pos - 1] != make_pair(-1, -1))
            {
                dpA[pos].first = dpA[pos - 1].first + 1;
                dpA[pos].second = dpA[pos - 1].second + 1;
            }
        }

        if (a[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
        {
            if (dpA[pos] == make_pair(-1, -1))
            {
                dpA[pos].first = dpB[pos - 1].first + 1;
                dpA[pos].second = dpB[pos - 1].second + 1;
            }
            else
            {
                dpA[pos].first = min(dpA[pos].first, dpB[pos - 1].first + 1);
                dpA[pos].second = max(dpA[pos].second, dpB[pos - 1].second + 1);
            }
        }

        if (b[pos] >= a[pos - 1])
        {
            if (dpA[pos - 1] != make_pair(-1, -1))
            {
                dpB[pos] = dpA[pos - 1];
            }
        }

        if (b[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
        {
            if (dpB[pos] == make_pair(-1, -1))
            {
                dpB[pos] = dpB[pos - 1];
            }
            else
            {
                dpB[pos].first = min(dpB[pos].first, dpB[pos - 1].first);
                dpB[pos].second = max(dpB[pos].second, dpB[pos - 1].second);
            }
        }
    }

    int curr = -1;

    //cout << dpA[2 * n].first << " " << dpA[2 * n].second << endl;
    //cout << dpB[2 * n].first << " " << dpB[2 * n].second << endl;

    if (dpA[2 * n].first <= n && n <= dpA[2 * n].second)
    {
        curr = 0;
    }

    if (dpB[2 * n].first <= n && n <= dpB[2 * n].second)
    {
        curr = 1;
    }

    if (curr == -1)
    {
        //cout << "here" << endl;
        cout << -1 << endl;
        return 0;
    }

    stack<char> result;
    result.push(char(curr + 'A'));

    int bound = (curr == 0 ? n - 1 : n);

    for (int pos = 2 * n - 1; pos >= 1; --pos)
    {
        int prv = (curr == 0 ? a[pos + 1] : b[pos + 1]);
        curr = -1;

        if (bound > 0 && prv >= a[pos] && dpA[pos].first <= bound && bound <= dpA[pos].second)
        {
            curr = 0;
            --bound;
        }
        else if (prv >= b[pos] && dpB[pos].first <= bound && bound <= dpB[pos].second)
        {
            curr = 1;
        }

        if (curr == -1)
        {
            cout << -1 << endl;
            return 0;
        }

        result.push(char(curr + 'A'));
    }

    while (!result.empty())
    {
        cout << result.top();
        result.pop();
    }

    cout << endl;

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 1 ms 6488 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 1 ms 6504 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 1 ms 6488 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 1 ms 6504 KB Output is correct
31 Correct 1 ms 6492 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6492 KB Output is correct
34 Runtime error 41 ms 12232 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -