Submission #258708

#	Time	Username	Problem	Language	Result	Execution time	Memory
258708		Kastanda	Building 4 (JOI20_building4)	C++11	0 / 100	9 ms	8320 KiB

building4

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006 * 2;
int n, m, A[N][2], dp[N][2], dp2[N][2], R[N];
pair < int , int > F[N];
int main()
{
        scanf("%d", &m); n = m + m;
        for (int w = 0; w < 2; w ++)
                for (int i = 1; i <= n; i ++)
                        scanf("%d", &A[i][w]);
        dp[1][0] = dp[1][1] = 1;
        for (int i = 2; i <= n; i ++)
                for (int w = 0; w < 2; w ++)
                {
                        if (A[i][w] >= A[i - 1][0])
                                dp[i][w] |= dp[i - 1][0];
                        if (A[i][w] >= A[i - 1][1])
                                dp[i][w] |= dp[i - 1][1];
                }
        if (!dp[n][0] && !dp[n][1])
                return !printf("-1\n");
        dp2[n][0] = dp2[n][1] = 1;
        for (int i = n - 1; i; i --)
                for (int w = 0; w < 2; w ++)
                {
                        if (A[i][w] <= A[i + 1][0])
                                dp2[i][w] |= dp2[i + 1][0];
                        if (A[i][w] <= A[i + 1][1])
                                dp2[i][w] |= dp2[i + 1][1];
                }
        if (!dp2[1][0] && !dp2[1][1])
                return !printf("-1\n");
        int Cnt0 = 0;
        memset(R, -1, sizeof(R));
        for (int i = 1; i <= n; i ++)
        {
                if ((!dp[i][0] || !dp2[i][0]) && (!dp[i][1] || !dp2[i][1]))
                        return !printf("-1\n");
                if (!dp[i][0] || !dp2[i][0])
                        R[i] = 1;
                else if (!dp[i][1] || !dp2[i][1])
                        R[i] = 0, Cnt0 ++;
        }
        vector < pair < int , int > > vec;
        for (int i = 1; i <= n; i ++)
                if (R[i] == -1)
                {
                        int r = i + 1;
                        while (r <= n && R[r] == -1 && max(A[i][0], A[i][1]) > min(A[i + 1][0], A[i + 1][1]))
                                r ++;
                        vec.push_back({i, r - 1});
                        i = r - 1;
                }
        int TMn = 0, TMx = 0;
        for (int j = 0; j < (int)vec.size(); j ++)
        {
                int l = vec[j].first;
                int r = vec[j].second;
                int cnt = 0;
                for (int i = l; i <= r; i ++)
                        if (A[i][0] < A[i][1])
                                cnt ++;
                int Mn = cnt, Mx = cnt;
                for (int i = r; i >= l; i --)
                {
                        if (A[i][0] < A[i][1])
                                cnt --;
                        else
                                cnt ++;
                        Mn = min(Mn, cnt);
                        Mx = max(Mx, cnt);
                }
                F[j] = {Mn, Mx};
                TMn += Mn;
                TMx += Mx;
        }
        if (Cnt0 + TMn > m || Cnt0 + TMx < m)
                return !printf("-1\n");
        for (int j = 0; j < (int)vec.size(); j ++)
        {
                assert(Cnt0 + TMn <= m);
                TMn -= F[j].first;
                int nd = m - Cnt0 - TMn;
                nd = min(nd, F[j].second);
                assert(nd >= F[j].first);
                Cnt0 += nd;
                int cnt = 0;
                int l = vec[j].first;
                int r = vec[j].second;
                for (int i = l; i <= r; i ++)
                        if (A[i][0] < A[i][1])
                                R[i] = 0, cnt ++;
                        else
                                R[i] = 1;
                if (cnt == nd)
                        continue;
                for (int i = r; i >= l; i --)
                {
                        if (A[i][0] < A[i][1])
                                R[i] = 1, cnt --;
                        else
                                R[i] = 0, cnt ++;
                        if (cnt == nd)
                                break;
                }
        }
        for (int i = 1; i <= n; i ++)
                printf(R[i] ? "B" : "A");
        printf("\n");
        return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &m); n = m + m;
         ~~~~~^~~~~~~~~~
building4.cpp:12:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                         scanf("%d", &A[i][w]);
                         ~~~~~^~~~~~~~~~~~~~~~

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