Submission #211820

#	Time	Username	Problem	Language	Result	Execution time	Memory
211820		mjguru	Building 4 (JOI20_building4)	C++17	100 / 100	479 ms	42360 KiB

building4

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdio>


using namespace std;


typedef long long int lli;


const int MAXN = 2*500001;
const int INF = MAXN+MAXN;


lli val[MAXN][2];
int starting[MAXN][2], ending[MAXN][2];
int ans[MAXN];


int main() {

  int N;
  scanf("%d", &N);
  N += N;

  for (int i = 1 ; i <= N ; i++) {
    scanf("%lld", &val[i][0]);
  }
  for (int i = 1 ; i <= N ; i++) {
    scanf("%lld", &val[i][1]);
  }

  for (int i = 1 ; i <= N ; i++) {
    for (int j = 0 ; j < 2 ; j++) {
      starting[i][j] = ending[i][j] = INF;
      int add;
      if (j == 0) add = 1;
      else add = -1;
      for (int k = 0 ; k < 2 ; k++) {
        if (val[i-1][k] > val[i][j]) continue;
        if (starting[i-1][k] != INF) {
          if (starting[i][j] == INF) {
            starting[i][j] = starting[i-1][k]+add;
            ending[i][j] = ending[i-1][k]+add;
          } else {
            starting[i][j] = min(starting[i][j], starting[i-1][k]+add);
            ending[i][j] = max(ending[i][j], ending[i-1][k]+add);
          }
        }
      }
      //cerr << "starting[" << i << "][" << j << "] = " << starting[i][j] << "\n";
      //cerr << "ending[" << i << "][" << j << "] = " << ending[i][j] << "\n\n";
    }
  }

  int at = N, level = -1, score = 0;
  if (starting[N][0] != INF && starting[N][0] <= 0 && ending[N][0] >= 0) {
     level = 0; 
  }
  if (starting[N][1] != INF && starting[N][1] <= 0 && ending[N][1] >= 0) {
     level = 1; 
  }
  if (level == -1) {
    printf("-1\n");
    return 0;
  }
  ans[at] = level;
  while (at != 1) {
    int add;
    if (level == 0) {
      add = 1;
    } else {
      add = -1;
    }
    for (int k = 0 ; k < 2 ; k++) {
      if (val[at-1][k] > val[at][level]) continue;
      if (starting[at-1][k] <= score-add && ending[at-1][k] >= score-add) {
        score -= add;
        level = k;
        break;
      }
    }
    at--;
    ans[at] = level;
  }

  for (int i = 1 ; i <= N ; i++) {
    if (ans[i] == 0) {
      printf("A");
    } else {
      printf("B");
    }
  }
  printf("\n");
  

  

  return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
building4.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &val[i][0]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
building4.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &val[i][1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

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