Submission #249760

#	Time	Username	Problem	Language	Result	Execution time	Memory
249760		apfelsaft	Building 4 (JOI20_building4)	C++14	0 / 100	3 ms	512 KiB

building4

#include <stdio.h>
#include <algorithm>

#define N 1000100
int sufA[N][2];
int sufB[N][2];
int seqA[N];
int seqB[N];
char erg[N];

void calc(int n){
  sufA[n-1][0] = 1;
  sufA[n-1][1] = 0;
  sufB[n-1][1] = 0;
  sufB[n-1][1] = 1;
  for(int i = n-2;i>=0;i--){
    if(seqA[i] <= seqA[i+1]){
      sufA[i][0] = sufA[i+1][0] + 1;  
      sufB[i][0] = sufB[i+1][0];
    }
    if(seqA[i] <= seqB[i+1]){
      sufA[i][0] = std::max(sufA[i][0],sufA[i+1][1] + 1);  
      sufB[i][0] = std::max(sufB[i+1][1],sufB[i][0]);
    };
    if(seqB[i] <= seqB[i+1]){
      sufA[i][1] = sufA[i+1][1];  
      sufB[i][1] = sufB[i+1][1] + 1;
    };
    if(seqB[i] <= seqA[i+1]){
      sufA[i][1] = std::max(sufA[i+1][0],sufA[i][1]);  
      sufB[i][1] = std::max(sufB[i][1],sufB[i+1][0] + 1);
    };
  };  
};

int main(void){
  int n;  
  scanf("%d",&n);
  for(int i = 0;i<n*2;i++){
    scanf("%d",&seqA[i]);  
  };
  for(int i = 0;i<n*2;i++){
    scanf("%d",&seqB[i]);  
  };
  calc(n*2);

  int a = n;
  int b = n;
  int prev = 0;
  int pos = 1;
  int posA,posB;
  for(int i = 0;i<n*2&&pos;i++){
    posA = 0;
    posB = 0;
    if(sufA[i][0] >= a && sufB[i][0] >= b && seqA[i] >= prev && (n*2-i-sufB[i][0]-1) <= a && (n*2-i-sufA[i][0]-1 <= b) && a > 0){
      posA = 1;
    }
    if(sufB[i][1] >= b && sufA[i][1] >= a && seqB[i] >= prev && (n*2-i-sufB[i][1]-1 <= a) && (n*2-i-sufA[i][1]-1 <= b) && b > 0){
      posB = 1;
    };

    if(posB && posA){
      if(seqA[i] <= seqB[i])posB = 0;  
      else posA = 0;
    };
    if(posA){
      erg[i]='A';  
      a--;
      prev = seqA[i];
    }else if(posB){
      erg[i]='B';  
      b--;
      prev = seqB[i];
    }else{
      pos = 0;  
    };
  };
  if(pos){
    printf("%s\n",erg);
  }
  else printf("-1\n");
  return 0;
};

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
building4.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&seqA[i]);  
     ~~~~~^~~~~~~~~~~~~~~
building4.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&seqB[i]);  
     ~~~~~^~~~~~~~~~~~~~~

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