제출 #941706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941706		vjudge1	건물 4 (JOI20_building4)	C++17	100 / 100	269 ms	99888 KiB

building4

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

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

/*
iau mereu cel mai mic posibil si dau switch

daca v[i][min] <= v[i + 1][min] si v[i][max] >= v[i + 1][min] si v[i][max] <= v[i + 1][max] atunci daca schimb i, schimb si i+1

pot sa iau sufix la cel mai mare interval
sufixul e un interval de valori (se schimba cu 1 costul)
v[i][0] = minimu
v[i][1] = maximu

balance = A - B
*/

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  n *= 2;
  
  vector<bool> swappedv(n + 1), is_max(n + 1);
  vector<int> cost(n + 1);
  vector<vector<int>> v(n + 1, vector<int>(2));
  for (int i = 1; i <= n; ++i) cin >> v[i][0];
  for (int i = 1; i <= n; ++i) cin >> v[i][1];
  
  bool ok = true;
  int balance = 0, lastc = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[i][0] <= v[i][1]) {
      if (v[i][0] >= lastc) {
        balance += 1;
        cost[i] = -1;
        
        lastc = v[i][0];
      } else {
        ok &= (v[i][1] >= lastc);
        balance -= 1;
        cost[i] = 0;
        is_max[i] = true;
        
        lastc = v[i][1];
      }
    } else {
      swappedv[i] = true;
      swap(v[i][0], v[i][1]);
      if (v[i][0] >= lastc) {
        balance -= 1;
        cost[i] = 1;
        
        lastc = v[i][0];
      } else {
        ok &= (v[i][1] >= lastc);
        balance += 1;
        cost[i] = 0;
        is_max[i] = true;
        
        lastc = v[i][1];
      }
    }
  }
  
  if (!ok) {
    cout << "-1";
    return 0;
  }
  balance /= 2;
  
  vector<pi> segments;
  int st = 1;
  for (int dr = 1; dr < n; ++dr) {
    if (cost[dr] == 0) { // sunt deja max
      segments.pb({st, dr});
      st = dr + 1;
      continue;
    }
    
    if (v[dr][1] > v[dr + 1][1]) { // nu pot da swap la asta, segmentul e invalidat
      st = dr + 1;
      continue;
    }
    
    if (v[dr][1] > v[dr + 1][0]) continue; // trebuie sa dau swap si la urmatorul
    
    // segmentul se termina aici
    segments.pb({st, dr});
    st = dr + 1;
  }
  segments.pb({st, n});
  
  /*cout << endl << endl;
  for (int i = 1; i <= n; ++i) cout << is_max[i] << " ";*/
  /*cout << endl << endl << balance << endl;
  for (pi s : segments) {
    cout << s[0] << " " << s[1] << " | ";
    for (int i = s[0]; i <= s[1]; ++i) cout << cost[i] << " ";
    cout << endl;
  }
  cout << endl;*/
  
  for (pi s : segments) {
    int l = s[0], r = s[1];
    
    int suf = 0;
    if (balance < 0) {
      int maxi = 0, maxidx = r + 1;
      for (int i = r; i >= l; --i) {
        suf += cost[i];
        if (balance + suf <= 0 && suf > maxi) {
          maxi = suf;
          maxidx = i;
        }
      }
      for (int i = r; i >= maxidx; --i) is_max[i] = true;
      
      balance += maxi;
    } else if (balance > 0) {
      int mini = 0, minidx = r + 1;
      for (int i = r; i >= l; --i) {
        suf += cost[i];
        if (balance + suf >= 0 && suf < mini) {
          mini = suf;
          minidx = i;
        }
      }
      for (int i = r; i >= minidx; --i) is_max[i] = true;
      
      balance += mini;
    }
  }
  
  if (balance != 0) {
    cout << "-1";
    return 0;
  }
  
  for (int i = 1; i <= n; ++i) {
    bool is_a = true;
    if (swappedv[i]) is_a = !is_a;
    if (is_max[i]) is_a = !is_a;
    cout << (is_a ? 'A' : 'B');
  }
}

/*
2
42 14 97 89 
30 68 69 53
*/

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