Submission #381388

#	Time	Username	Problem	Language	Result	Execution time	Memory
381388		KULIKOLD	Hamburg Steak (JOI20_hamburg)	C++17	0 / 100	3 ms	492 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define x1 fdgfdgf
#define y1 fdhfdgfdg
#define endl '\n'
const ll DIM = 5E5+7;
const ll INF = 1E18;
ll A[2][DIM],ans[DIM];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    n*=2;
    ll last = 0;
    for(ll i = 1;i<=n;++i) {
        cin>>A[0][i];
    }
    for(ll i = 1;i<=n;++i){
        cin>>A[1][i];
    }
    ll cnt[] = {0,0};
    for(ll i = 1;i<=n;++i){
        if (min(A[0][i],A[1][i])>=last){
            if (A[0][i]<A[1][i])ans[i] = 0,++cnt[0];
            else ans[i] = 1,++cnt[1];
            last = min(A[0][i],A[1][i]);
        }
        else if (max(A[0][i],A[1][i])>=last){
            if (A[0][i]>A[1][i])ans[i] = 0,++cnt[0];
            else ans[i] = 1,++cnt[1];
            last = max(A[0][i],A[1][i]);
        }
        else{
            cout<<"-1\n";
            return 0;
        }
    }
    A[0][n+1] = A[1][n+1] = INF;
    for(ll i = n;i>=1;--i){
        if (cnt[0]<cnt[1] && ans[i]==1 && A[0][i]<=A[ans[i+1]][i+1]  && A[0][i]>=A[ans[i-1]][i-1]){
            ++cnt[0];
            --cnt[1];
            ans[i] = 0;
        }
        if (cnt[1]<cnt[0] && ans[i]==0 && A[1][i]<=A[ans[i+1]][i+1]  && A[1][i]>=A[ans[i-1]][i-1]){
            ++cnt[1];
            --cnt[0];
            ans[i] = 1;
        }
    }
    if (cnt[1]!=cnt[0]){
        cout<<"-1\n";
    }
    for(ll i = 1;i<=n;++i){
        if (ans[i])cout<<'B';
        else cout<<'A';
    }
    cout<<endl;
    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79