제출 #249893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249893		apfelsaft	Building 4 (JOI20_building4)	C++14	100 / 100	398 ms	42988 KiB

building4

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

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

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]);  
  };
  int pos = 1;
  memset(sufA,-1,sizeof(sufA));
  memset(sufB,-1,sizeof(sufB));
  sufA[0][0] = 1;
  sufA[0][1] = 1;
  sufB[0][0] = 0;
  sufB[0][1] = 0;
  int a = n;
  int b = n;
  for(int i = 1;i<n*2;i++){
    if(seqA[i] >= seqA[i-1] && sufA[i-1][0] != -1){
      sufA[i][0] = sufA[i-1][0]+1;
      sufA[i][1] = sufA[i-1][1]+1;
    };  
    if(seqA[i] >= seqB[i-1] && sufB[i-1][0] != -1){
      if(sufA[i][0] != -1){
	sufA[i][0] = std::min(sufA[i][0],sufB[i-1][0] + 1);  
	sufA[i][1] = std::max(sufA[i][1],sufB[i-1][1] + 1);  
      }else{
	sufA[i][0] = sufB[i-1][0]+1;
	sufA[i][1] = sufB[i-1][1]+1;
      };
    };
    if(seqB[i] >= seqA[i-1] && sufA[i-1][0] != -1){
      sufB[i][0] = sufA[i-1][0];  
      sufB[i][1] = sufA[i-1][1];  
    };
    if(seqB[i] >= seqB[i-1] && sufB[i-1][0] != -1){
      if(sufB[i][0] != -1){
	sufB[i][0] = std::min(sufB[i][0],sufB[i-1][0]);  
	sufB[i][1] = std::max(sufB[i][1],sufB[i-1][1]);  
      }else{
	sufB[i][0] = sufB[i-1][0];  
	sufB[i][1] = sufB[i-1][1];  
      };
    };
    //printf("%d %d %d %d %d\n",i,sufA[i][0],sufA[i][1],sufB[i][0],sufB[i][1]);
  };
  int prev = 2000000000;
  int posA,posB;
  for(int i = 2*n-1;i>=0&&pos;i--){
    posA = 0;
    posB = 0;
    if(sufA[i][0] <= a && sufA[i][1] >= a && seqA[i] <= prev){
      posA = 1;
    }else if(sufB[i][0] <= a && sufB[i][1] >= a && seqB[i] <= prev){
      posB = 1;
    }else{
      pos = 0;
    };  
    if(posA && posB){
      if(seqA[i] >= seqB[i])posB = 0;  
      else posA = 0;
    };
    if(posA){
      prev = seqA[i];
      erg[i] = 'A';  
      a--;
    }else{
      prev = seqB[i];
      erg[i] = 'B';  
    };
  };
  if(pos){
    printf("%s\n",erg);
  }
  else printf("-1\n");
  return 0;
};

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'int main()':
building4.cpp:29:7: warning: unused variable 'b' [-Wunused-variable]
   int b = n;
       ^
building4.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
building4.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&seqA[i]);  
     ~~~~~^~~~~~~~~~~~~~~
building4.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&seqB[i]);  
     ~~~~~^~~~~~~~~~~~~~~

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