Submission #1297853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297853		StefanSebez	Building 4 (JOI20_building4)	C++20	100 / 100	248 ms	25948 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int inf=1e9;
void chmx(int &x,int y){x=max(x,y);}
void chmn(int &x,int y){x=min(x,y);}
int main(){
    int n;scanf("%i",&n);n*=2;
    int a[2][n+10];
    for(int i=0;i<=1;i++) for(int j=0;j<n;j++) scanf("%i",&a[i][j]);
    int maks[2][n+10],mn[2][n+10];
    maks[0][0]=mn[0][0]=1;
    maks[1][0]=mn[1][0]=-1;
    for(int i=1;i<n;i++){
        maks[0][i]=-inf;
        mn[0][i]=inf;
        if(a[0][i-1]<=a[0][i]) chmx(maks[0][i],maks[0][i-1]+1),chmn(mn[0][i],mn[0][i-1]+1);
        if(a[1][i-1]<=a[0][i]) chmx(maks[0][i],maks[1][i-1]+1),chmn(mn[0][i],mn[1][i-1]+1);
        maks[1][i]=-inf;
        mn[1][i]=inf;
        if(a[0][i-1]<=a[1][i]) chmx(maks[1][i],maks[0][i-1]-1),chmn(mn[1][i],mn[0][i-1]-1);
        if(a[1][i-1]<=a[1][i]) chmx(maks[1][i],maks[1][i-1]-1),chmn(mn[1][i],mn[1][i-1]-1);
    }
    int x=-1,y=n-1;
    if(mn[0][n-1]<=0&&0<=maks[0][n-1]) x=0;
    if(mn[1][n-1]<=0&&0<=maks[1][n-1]) x=1;
    if(x==-1) printf("-1\n");
    else{
        string res;
        int sum=0;
        while(y>=0){
            if(x==0) sum++;
            else sum--;
            if(x==0) res.pb('A');
            else res.pb('B');
            if(y<=0)break;
            if(a[0][y-1]<=a[x][y]&&mn[0][y-1]+sum<=0&&0<=maks[0][y-1]+sum)x=0,y--;
            else if(a[1][y-1]<=a[x][y]&&mn[1][y-1]+sum<=0&&0<=maks[1][y-1]+sum)x=1,y--;
            else break;
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
    }
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:13:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     int n;scanf("%i",&n);n*=2;
      |           ~~~~~^~~~~~~~~
building4.cpp:15:53: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     for(int i=0;i<=1;i++) for(int j=0;j<n;j++) scanf("%i",&a[i][j]);
      |                                                ~~~~~^~~~~~~~~~~~~~~

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