Submission #1166999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166999		tvgk	Building 4 (JOI20_building4)	C++20	0 / 100	0 ms	324 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7, inf = 1e9 + 7;

bool id[mxN];
int n, a[mxN][3], mx[mxN], mn[mxN], ans[mxN];
vector<ii> v;

int cvert(bool j)
{
    if (j == 1)
        return 1;
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    n *= 2;
    for (int i = 0; i <= 1; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[j][i];
            ans[j] = -1;
            id[j] = a[j][1] >= a[j][0];
        }
    }
    a[n + 1][0] = a[n + 1][1] = inf;

    int sum = 0;
    for (int i = n - 1; i > 0; i--)
    {
        if (a[i][id[i]] > a[i + 1][id[i + 1]])
        {
            id[i] = ans[i] = id[i] ^ 1;
            sum += cvert(ans[i]);
        }
    }

    int l = 1;
    for (int i = 1; i <= n; i++)
    {
        if (min(a[i][0], a[i][1]) > max(a[i][0], a[i][1]))
        {
            cout << -1;
            return 0;
        }

        if (ans[i] != -1)
        {
            if (l < i)
                v.push_back({l, i - 1});
            l = i + 1;
        }
        if (a[i][id[i]] <= min(a[i + 1][0], a[i + 1][1]))
        {
            if (l <= i)
                v.push_back({l, i});
            l = i + 1;
        }
    }

    for (int j = 1; j <= v.size(); j++)
    {
        int cur = 0;
        for (int i = v[j - 1].fi; i <= v[j - 1].se; i++)
            cur -= cvert(id[i]);

        mn[j] = mx[j] = cur;
        for (int i = v[j - 1].fi; i <= v[j - 1].se; i++)
        {
            id[i] ^= 1;
            if (a[i - 1][id[i - 1]] > a[i][id[i]])
                break;

            cur -= 2 * cvert(id[i]);
            mn[j] = min(mn[j], cur);
            mx[j] = max(mx[j], cur);
        }
        mn[j] += mn[j - 1];
        mx[j] += mx[j - 1];
    }

    if (sum < mn[v.size()] || mx[v.size()] < sum)
    {
        cout << -1;
        return 0;
    }

    for (int j = v.size() - 1; j >= 0; j--)
    {
        for (int i = v[j].fi; i <= v[j].se; i++)
        {
            ans[i] = a[i][1] >= a[i][0];
            sum += cvert(ans[i]);
        }

        for (int i = v[j].fi; i <= v[j].se; i++)
        {
            if (mn[j] <= sum && sum <= mx[j])
                break;

            ans[i] ^= 1;
            sum += 2 * cvert(ans[i]);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << char('A' + ans[i]);
}

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