Submission #414852

#	Time	Username	Problem	Language	Result	Execution time	Memory
414852		NintsiChkhaidze	Building 4 (JOI20_building4)	C++14	100 / 100	317 ms	41412 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
#define ll  long long
#define s second
#define f first
using namespace std;
const int N = 1000005;
int a[N],b[N];
pair<int,int> dp[4][N];
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
 
    for (int i=1;i<=2*n;i++) cin>>a[i];
    for (int i=1;i<=2*n;i++){
        cin>>b[i];
        dp[1][i] = {2e9,0};
        dp[2][i] = {2e9,0};
    }
    
    dp[1][1] = {1,1}; 
    dp[2][1] = {0,0};
    for (int i=1;i<=2*n;i++){
        if (a[i] >= a[i - 1]) dp[1][i] = {min(dp[1][i].f,dp[1][i-1].f + 1),max(dp[1][i].s,dp[1][i-1].s + 1)};   
        if (a[i] >= b[i - 1]) dp[1][i] = {min(dp[1][i].f,dp[2][i-1].f + 1),max(dp[1][i].s,dp[2][i-1].s + 1)};    
        if (b[i] >= a[i - 1]) dp[2][i] = {min(dp[2][i].f,dp[1][i-1].f),max(dp[2][i].s,dp[1][i-1].s)}; 
        if (b[i] >= b[i - 1]) dp[2][i] = {min(dp[2][i].f,dp[2][i-1].f),max(dp[2][i].s,dp[2][i-1].s)};    
    }
    int c=0;
    if (dp[1][2*n].f <= n && dp[1][2*n].s >= n) c=1;
    if (dp[2][2*n].f <= n && dp[2][2*n].s >= n) c=1;
    if (!c) {cout<<-1; return 0;}
    
    string s = "";
    int cnta = n,l=1e9;
    
    for (int i=2*n;i>=1;i--){
        if (a[i] <= l && dp[1][i].f <= cnta && dp[1][i].s >= cnta) cnta--,l=a[i],s+='A';
        else l = b[i],s+='B';
    }
    reverse(s.begin(),s.end());
    cout<<s;
}

Compilation message (stderr)

building4.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main (){
      | ^~~~

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