Submission #304950

#	Time	Username	Problem	Language	Result	Execution time	Memory
304950		LifeHappen__	Building 4 (JOI20_building4)	C++14	11 / 100	65 ms	8640 KiB

building4

#include<bits/stdc++.h>

using namespace std;

#define forinc(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define fordec(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

const int N=5e5+5;
int n,a[N][2],dd[N][2];
ii f[N][2];

void dfs(int i,int j){
   if(dd[i][j]) return;
   dd[i][j]=1;
   int mi=1e9, ma=-1e9;
   if(a[i][j]<=a[i+1][0]){
      dfs(i+1,0);
      mi=min(mi,f[i+1][0].fi+1); ma=max(ma, f[i+1][0].se+1);
   }
   if(a[i][j]<=a[i+1][1]){
      dfs(i+1,1);
      mi=min(mi,f[i+1][1].fi); ma=max(ma, f[i+1][1].se);
   }
   f[i][j]={mi,ma};
}

int32_t main(){
   fasty;

   #define task "build"
   if(fopen(task".in","r")) freopen(task".in","r",stdin);

   cin>>n; n*=2;
   forinc(_,0,1) forinc(i,1,n) cin>>a[i][_];
   dd[n][0]=dd[n][1]=1;
   dfs(0,0);
   if(f[0][0].fi>n/2 || f[0][0].fi>f[0][0].se) return cout<<-1,0;

   int pre=0, re=n/2;
   forinc(i,1,n){
      if(a[i][0]>=a[i-1][pre] && f[i][0].fi<=re-1 && re-1<=f[i][0].se){
         pre=0;
         re--;
         cout<<"A";
      }else{
         pre=1;
         cout<<"B";
      }
   }
}

Compilation message (stderr)

building4.cpp: In function 'int32_t main()':
building4.cpp:41:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |    if(fopen(task".in","r")) freopen(task".in","r",stdin);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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