제출 #219031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219031		Nightlight	건물 4 (JOI20_building4)	C++14	0 / 100	5 ms	384 KiB

building4

#include <bits/stdc++.h>
using namespace std;

int N;
int fix[1000005][2];
//apakah fixed
int to[1000005][2];
//menyimpan lokasi bridge terdekat (A ke B) dan (B ke A)
int A[1000005][2];
//tinggi building
int b[2];
//banyak yang diperlukan untuk setiap A B
bool rc[1000005][2];
//dp pertama nyimpan semua path valid

void DFS(int u, int i) {
  if(u == N) {
    rc[u][i] = 1;
    return;
  }
  if(rc[u][i]) return;
  if(A[u][i] <= A[u + 1][i]) {
    DFS(u + 1, i);
    rc[u][i] |= rc[u + 1][i];
  }
  if(A[u][i] <= A[u + 1][!i]) {
    DFS(u + 1, !i);
    rc[u][i] |= rc[u + 1][!i];
  } 
}

int main() {
//  freopen("inp", "r", stdin);
  scanf("%d", &N);
  N <<= 1;
  for(int i = 1; i <= N; i++) {
    scanf("%d", &A[i][0]);
  }
  for(int i = 1; i <= N; i++) {
    scanf("%d", &A[i][1]);
  }
  A[N + 1][0] = 2e9, A[N + 1][1] = 2e9; 
  DFS(1, 0);
  DFS(1, 1);
  if(!rc[1][0] && !rc[1][1]) {
    puts("-1");
    return 0; 
  }
  b[0] = N >> 1, b[1] = N >> 1;
  for(int i = 1; i <= N; i++) {
    if(rc[i][0] ^ rc[i][1]) {
      b[0] -= rc[i][0];
      b[1] -= rc[i][1];
    }
    if(A[i - 1][0] <= A[i][1] && rc[i - 1][0] && rc[i][1]) {
      to[i - 1][0] = i - 1;
    }
    if(A[i - 1][1] <= A[i][0] && rc[i - 1][1] && rc[i][0]) {
      to[i - 1][1] = i - 1;
    }
  }
/*  for(int i = 1; i <= N; i++) {
    cout << to[i][0] << " ";
  }
  puts("");
  for(int i = 1; i <= N; i++) {
    cout << to[i][1] << " ";
  }
  puts("");*/
  int mn[2];
  for(int i = N; i > 0; i--) {
    if(rc[i][0]) {
      if(to[i][0]) mn[0] = to[i][0];
      else to[i][0] = mn[0];
    }
    //ada bridge baru A ke B
    if(rc[i][1]) {
      if(to[i][1]) mn[1] = to[i][1];
      else to[i][1] = mn[1];
    }
    //ada bridge baru B ke A
  }
  if((b[0] < 0) || (b[1] < 0)) {
    puts("-1");
    return 0;
  }
  int last = 0;
  for(int i = 1; i <= N; i++) {
    if(rc[i][0] ^ rc[i][1]) {
      //kalau fixed
      putchar((rc[i][0] ? 'A' : 'B'));
      last = rc[i][1];
      continue;
    }
    //greedy A duluan kalau A dah habis baru B semua
    if(last == 0) {
      if(to[i][0] - i + 1 <= b[0]) {
        //jika bridge (A ke B) terdekat dan posisi sekarang jaraknya kurang dari jumlah 'A' yang diperlukan maka ambil aja
        b[0]--;
        putchar('A');
      }else {
        last = 1;
        b[1]--;
        putchar('B');
      }
    }else if(last == 1) {
      if(to[i - 1][1] == i - 1 && to[i][0] - i + 1 <= b[0]) {
        //jika sebelumnya ada bridge (B ke A) dan jarak bridge (A ke B) dan (B ke A) terdekat kurang dari jumlah 'A' yang diperlukan
        b[0]--;
        putchar('A');
        last = 0;
      }else {
        b[1]--;
        putchar('B');
      }
    }
  } 
}

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

building4.cpp: In function 'int main()':
building4.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
building4.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &A[i][0]);
     ~~~~~^~~~~~~~~~~~~~~~
building4.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &A[i][1]);
     ~~~~~^~~~~~~~~~~~~~~~
building4.cpp:80:21: warning: 'mn[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
       else to[i][1] = mn[1];
            ~~~~~~~~~^~~~~~~
building4.cpp:75:21: warning: 'mn[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
       else to[i][0] = mn[0];
            ~~~~~~~~~^~~~~~~

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