Submission #647726

#	Time	Username	Problem	Language	Result	Execution time	Memory
647726		beaconmc	Building 4 (JOI20_building4)	C++14	100 / 100	841 ms	115920 KiB

building4

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

pair<ll,ll> dp[1000001][2];
ll a[1000001];
ll b[1000001];

vector<ll> edges[2000001];

ll n;

// dp[i][j] means the number of type 0 buildings we can have when we are at the ith city, and j is
// the type of building we are at when we are at the ith city.

int main(){
  cin >> n;
  FOR(i,1,2*n+1){
    cin >> a[i];
  }
  FOR(i,1,2*n+1){
    cin >> b[i];
  }
  FOR(i,0,2*n+1){
    dp[i][0] = {1000000000,-1000000000};
    dp[i][1] = {1000000000,-1000000000};
  }

  dp[0][0] = dp[0][1] = {0, 0};

  FOR(i,1,2*n+1){

    if (a[i] >= a[i-1]){

      dp[i][0].first = min(dp[i][0].first, dp[i-1][0].first);
      dp[i][0].second = max(dp[i][0].second, dp[i-1][0].second);
    }

    if (a[i] >= b[i-1]){

      dp[i][0].first = min(dp[i][0].first, dp[i-1][1].first);
      dp[i][0].second = max(dp[i][0].second, dp[i-1][1].second);
    }

    if (b[i] >= b[i-1]){
      dp[i][1].first = min(dp[i][1].first, dp[i-1][1].first);
      dp[i][1].second = max(dp[i][1].second, dp[i-1][1].second);
    }

    if (b[i] >= a[i-1]){
      dp[i][1].first = min(dp[i][1].first, dp[i-1][0].first);
      dp[i][1].second = max(dp[i][1].second, dp[i-1][0].second);
    } 

    dp[i][0].first++;
    dp[i][0].second++;

  }

  // FOR(i,0,2*n+1){
  //   cout << dp[i][0].first << " " << dp[i][0].second << endl;
  // }

  string ans = "";
  ll cur = 1000000000;

  FORNEG(i,2*n, 0){

    if (a[i] > cur || dp[i][0].first > n || dp[i][0].second < n){

      if (b[i] > cur || dp[i][1].first > n || dp[i][1].second < n){
        cout << -1;
        return 0;
      }
      ans += "B", cur = b[i];
    }else ans += "A", cur = a[i],n-=1;
  }
  reverse(ans.begin(), ans.end());
  cout << ans;






}

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