Submission #1039799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039799		pera	Building 4 (JOI20_building4)	C++17	100 / 100	1724 ms	48288 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1 , oo = 1e9;
int n;
int A[N][2] , mn[N][2] , mx[N][2];
int main(){
   cin >> n;
   n *= 2;
   for(int x = 0;x < 2;x ++){
      for(int i = 1;i <= n;i ++){
         cin >> A[i][x];
      }
   }
   for(int i = 1;i <= n;i ++){
      for(int x = 0;x < 2;x ++){
         mn[i][x] = oo;
         mx[i][x] = 0;
      }
   }
   A[0][0] = A[0][1] = 0;
   for(int i = 1;i <= n;i ++){
      for(int x = 0;x < 2;x ++){
         for(int y = 0;y < 2;y ++){
            if(A[i][x] >= A[i - 1][y]){
               mn[i][x] = min(mn[i][x] , mn[i - 1][y] + !x);
               mx[i][x] = max(mx[i][x] , mx[i - 1][y] + !x);
            }
         }
         //cout << mn[i][x] << " " << mx[i][x] << endl;
      }
      //cout << endl;
   }
   for(int x = 0;x < 2;x ++){
      if(mn[n][x] <= n / 2 && n / 2 <= mx[n][x]){
         int ans[n + 1];
         int v = n , e = x , cnt = 0;
         while(v >= 1){
            ans[v] = e;
            cnt += !e;
            --v;
            if(A[v + 1][e] >= A[v][0] && mn[v][0] + cnt <= n / 2 && n / 2 <= mx[v][0] + cnt){
               e = 0;
            }else{
               e = 1;
            }
         }
		   for(int i = 1;i <= n;i ++){
           cout << (!ans[i] ? 'A' : 'B');
         }
         cout << endl;
         return 0;
      }
   }
   cout << -1 << endl;
}

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