Submission #1097249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097249		MrPavlito	Building 4 (JOI20_building4)	C++17	100 / 100	238 ms	108236 KiB

building4

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 5e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

int n;
vector<vector<pii>> dp(MAXN*2, vector<pii>(2, {inf,-inf}));

bool check(pii p, int c)
{
    if(p.fi <= c && p.sc >=c)return 1;
    return 0;
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n;
        n<<=1;
        vector<int>a(n);
        vector<int>b(n);
        for(int i=0; i<n; i++)cin >> a[i];
        for(int i=0; i<n; i++)cin >> b[i];
        dp[0][0] = {1,1};
        dp[0][1] = {0,0};

        for(int i=1; i<n; i++)
        {
            ///gornji deo
            if(b[i-1] <= a[i])
            {
                dp[i][0].fi = min(dp[i][0].fi, dp[i-1][1].fi + 1);
                dp[i][0].sc = max(dp[i][0].sc, dp[i-1][1].sc + 1);
            }
            if(a[i-1] <= a[i])
            {
                dp[i][0].fi = min(dp[i][0].fi, dp[i-1][0].fi + 1);
                dp[i][0].sc = max(dp[i][0].sc, dp[i-1][0].sc + 1);
            }
            /// donji deo
            if(b[i-1] <= b[i])
            {
                dp[i][1].fi = min(dp[i][1].fi, dp[i-1][1].fi);
                dp[i][1].sc = max(dp[i][1].sc, dp[i-1][1].sc);
            }
            if(a[i-1] <= b[i])
            {
                dp[i][1].fi = min(dp[i][1].fi, dp[i-1][0].fi);
                dp[i][1].sc = max(dp[i][1].sc, dp[i-1][0].sc);
            }
        }
        //for(int i=0; i<n; i++)cout << dp[i][0].fi << ":" << dp[i][0].sc << "  ";cout << endl;
        //for(int i=0; i<n; i++)cout << dp[i][1].fi << ":" << dp[i][1].sc << "  ";cout << endl;
        if(!(check(dp[n-1][0], n/2) || check(dp[n-1][1], n/2) ))cout << -1 << endl;
        else
        {
            vector<char> rez;
            int i = n-1;
            int j = 0;
            if(!check(dp[n-1][0], n/2))j = 1;
            int cnt = n/2;
            while(i>=0)
            {
                rez.pb('A' + j);
                cnt -= (1-j);
                if(i ==0)break;
                if(j == 0)
                {
                    if(check(dp[i-1][0], cnt) && a[i] >= a[i-1]) j = 0;
                    else if(check(dp[i-1][1], cnt)&& a[i] >= b[i-1]) j = 1;
                    else
                    {
                        cout << -1 << endl;
                        return 0;
                    }
                }
                else
                {
                    if(check(dp[i-1][0], cnt) && b[i] >= a[i-1]) j = 0;
                    else if(check(dp[i-1][1], cnt)&& b[i] >= b[i-1]) j = 1;
                    else
                    {
                        cout << -1 << endl;
                        return 0;
                    }
                }

                i--;
            }
            reverse(all(rez));
            for(auto x: rez)cout << x;cout << endl;
        }


    }
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:106:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |             for(auto x: rez)cout << x;cout << endl;
      |             ^~~
building4.cpp:106:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |             for(auto x: rez)cout << x;cout << endl;
      |                                       ^~~~

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